Labels

Project Euler #93: Arithmetic expressions

Question
By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.
For example,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)
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 < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

Answer : 1258

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
    
    private static final double EPSILON = 0.00001;
    
    private static void eval(ArrayList<Double> numbers, boolean[] used) {
        if(numbers.size() == 1) {
            double result = numbers.get(0) + EPSILON;
            if((result % 1.0) <= 10 * EPSILON) {
                int index = (int) (result + EPSILON);
                if(index >= 0 && index < used.length) {
                    used[index] = true;
                }
            }
        } else {
            //step 2
            ArrayList<Double> next;
            for(int i = 0; i < numbers.size(); i++) {
                for(int j = i + 1; j < numbers.size(); j++) {
                    double a = numbers.get(i);
                    double b = numbers.get(j);
                    next = new ArrayList<>(numbers);
                    next.remove(j);
                    next.remove(i);
                    next.add(a + b);
                    eval(next, used);
                    int back = next.size() - 1;
                    next.set(back, a - b);
                    eval(next, used);
                    next.set(back, b - a);
                    eval(next, used);
                    next.set(back, a * b);
                    eval(next, used);
                    if(b != 0) {
                        next.set(back, a / b);
                        eval(next, used);
                    }
                    if(a != 0) {
                        next.set(back, b / a);
                        eval(next, used);
                    }
                }
            }
        }
    }
    
    private static int getSequenceLength(ArrayList<Double> numbers) {
        boolean[] used = new boolean[1000];
        eval(numbers, used);
        int result = 0;
        while(used[result + 1]) {
            result++;
        }
        return result;
    }
    
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();
            ArrayList<Double> numbers = new ArrayList<>();
            while(N-- > 0) {
                numbers.add(sc.nextDouble());
            }
            System.out.println(getSequenceLength(numbers));
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts