Project Euler Problem 93 Solution

Project Euler Problem 93 Statement

By using each of the digits from the set, $\{1, 2, 3, 4\}$, exactly once, and making use of the four arithmetic operations ($+, -, \times, /$) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

$$\begin{align} 8 &= (4 \times (1 + 3)) / 2\\ 14 &= 4 \times (3 + 1 / 2)\\ 19 &= 4 \times (2 + 3) - 1\\ 36 &= 3 \times 4 \times (2 + 1) \end{align}$$

Note that concatenations of the digits, like $12 + 34$, are not allowed.

Using the set, $\{1, 2, 3, 4\}$, it is possible to obtain thirty-one different target numbers of which $36$ is the maximum, and each of the numbers $1$ to $28$ can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, $a \lt b \lt c \lt d$, for which the longest set of consecutive positive integers, $1$ to $n$, can be obtained, giving your answer as a string: abcd.

Solution

HackerRank Project Euler Problem 93 overview:

Given 1—5 digits, we can use the four basic arithmetic operations (+, −, ×, ÷) on any pair of numbers at a time, combining results in all possible ways (with parentheses dictating the order of operations), to see which integers can be formed. We want to find, starting at 1 and going upward, how many consecutive integers can be formed.

Solution Summary

The solution uses a recursive function to generate every possible result by combining pairs of numbers with the basic operations (+, −, ×, ÷) in all orders and valid parentheses placements. Starting with 1—5 input digits, it systematically removes two at a time, replaces them with their computed result, and recurses until only one value remains. All near-integer values (within $1\times 10^{-9}$) are collected in a set. Then, starting from 1, the code checks consecutive integers and stops at the first number not in this set, returning the largest consecutive integer that can be formed.

Solution Detail

The function f(v):
If there’s only one number in the list v[], it just returns that number in a set: {v[0]}. Otherwise, f() picks every pair (a, b) in the list and computes:
- $a + b$
- $|a - b|$
- $a \times b$
- $a\div b$ (if $b \neq 0$)
- $b\div a$ (if $a \neq 0$)
After computing one of these results (for example, $a + b$), it appends that result to the remaining numbers and recursively calls f() again. This is essentially exploring every possible way to insert parentheses and apply operations among the 1—5 digits.
Gathering reachable integers:
After the function f(S) returns all possible real-number results, we filter to include only those very close (within $10^{-9}$) to an integer, storing the rounded integer in numbers. Hence, numbers is the set of all integer values formable from the 1—5 digits.
Finding the largest block of consecutive integers:
We start at n = 1 and increment while n is in numbers. As soon as we find an n that is not in numbers, we stop. The problem wants the largest integer $n - 1$ such that all integers from 1 up to $n - 1$ are in numbers. So we print n - 1.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 93

Given a set of $m$, (1 ≤ m ≤ 5) distinct digits, $S$, find the largest possible integer $n$ such that each integer from $1$ to $n$ is expressible using elements of $S$ and following the above rules. If $1$ is also not expressible, output $0$ instead.

Python Source Code

def f(v):
    if len(v)==1: return{v[0]}
    s = set()
    for i in range(len(v)):
        for j in range(i+1, len(v)):
            a,b = v[i],v[j]
            r = [v[k] for k in range(len(v)) if k not in (i,j)]
            s|= f(r+[a+b])
            s|= f(r+[abs(a-b)])
            s|= f(r+[a*b])
            if b>0: s|= f(r+[a/b])
            if a>0: s|= f(r+[b/a])
    return s

input()  # dgas
d = list(map(int, input().split()))
numbers = {round(x) for x in f(d) if abs(x - round(x)) < 1e-9}
n = 1
while n in numbers: n+= 1
print(n-1)