Project Euler Problem 33 Solution

Project Euler Problem 33 Statement

The fraction $49/98$ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that $49/98 = 4/8$, which is correct, is obtained by cancelling the $9$s.

We shall consider fractions like, $30/50 = 3/5$, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution

By exhaustively searching through all digit insertions and combinations, the program ensures it finds every instance of these curious equivalences. While the concept of "digit cancelling fractions" is somewhat whimsical, the brute-force method is straightforward and reliable for the input sizes typical of Project Euler and HackerRank challenges.

An approach to solving this problem

Input and Parameters
The program reads two numbers $(N, K)$ that represent how many digits each fraction component has, and how many digits to "cancel" or insert. This generalizes the simpler, single-digit example in Project Euler #33, allowing you to explore multi-digit numerators and denominators.
Generating Base Numbers
For the fraction's numerator and denominator, the code generates all possible "base" digit sequences of length $(n-k)$, excluding the all-zero sequence. These base sequences represent the original, un-cancelled part of the fraction.
Inserting (or "Cancelling") Digits
The code also generates all possible $K$-digit combinations (from 1–9) to interleave into each base sequence. By systematically inserting these digits at every possible position in the base sequence, it mimics "digit insertion," which corresponds to "digit cancelling" from another perspective.
Checking for Curiosity
For each pair of generated numbers, the program checks if two different fractions $\frac{n_1}{d_1}$ and $\frac{n_2}{d_2}$ are essentially the same value, i.e., $n_1 \times d_2 = n_2 \times d_1$. These matchups correspond to the "digit cancelling" phenomenon when they simplify correctly.
Summation of Results
Finally, the valid fractions are collected, and the code sums up their denominators (or whichever total is requested). The print statement at the end produces the result required by HackerRank or a typical Project Euler solution format.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 33

HackerRank Project Euler 33: Sum all the Numerators and the Denominators of the original fractions, and print them separated by a space.

Python Source Code

from itertools import combinations, combinations_with_replacement as cwr, product

def f():
    # Read inputs
    n, k = map(int, input().split())
    
    # Helper function: given a starting string `st` and a tuple of digits,
    # returns all possible ways to interleave those digits into `st`.
    def expansions(st, digits):
        res = {st}
        for d in digits:
            # For each string in the current set, insert digit d at every possible position
            res = { s[:i] + str(d) + s[i:] for s in res for i in range(len(s) + 1) }
        return res
    
    # All possible k-digit "cancel" sets (e.g. digits to be inserted)
    cancel_sets = cwr(range(1, 10), k)
    
    # All base tuples of length n-k, excluding the all-zero tuple
    bases = [p for p in product(range(10), repeat=n - k) if any(p)]
    
    valid_fractions = set()
    
    # For each possible cancel set
    for cset in cancel_sets:
        pairs = []
        
        # Build (original_number, expanded_number) pairs
        for b in bases:
            b_str = ''.join(map(str, b))
            b_val = int(b_str)
            
            # Generate all expansions for this base string and cancel-set digits
            for e_str in expansions(b_str, cset):
                # Skip expansions that begin with '0' (invalid as integer representations)
                if e_str[0] != '0':
                    pairs.append((b_val, int(e_str)))
        
        # Compare pairs in combination to find valid 'fraction-cancelling' relationships
        for (n1, d1), (n2, d2) in combinations(pairs, 2):
            if n1 < n2 and n1 * d2 == n2 * d1:
                valid_fractions.add((d1, d2))
    
    # Sum up denominators separately
    print(sum(x for x, _ in valid_fractions), sum(y for _, y in valid_fractions))
f()