We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
public class LongestSequence {
private static final double EPSILON = 0.00001;
// Evaluate all arithmetic operations of any two elements of "numbers", mark their result in "used" as true
private static void eval(List<Double> numbers, boolean[] used) {
if (numbers.size() == 1) {
double result = numbers.get(0) + EPSILON;
if (Math.abs(result % 1) > 10 * EPSILON) return;
int index = (int) (result + EPSILON);
if (index >= 0 && index < used.length) used[index] = true;
return;
}
List<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);
next.set(next.size() - 1, a - b);
eval(next, used);
next.set(next.size() - 1, b - a);
eval(next, used);
next.set(next.size() - 1, a * b);
eval(next, used);
if (b != 0) {
next.set(next.size() - 1, a / b);
eval(next, used);
}
if (a != 0) {
next.set(next.size() - 1, b / a);
eval(next, used);
}
}
}
}
// Evaluate all expressions and count how many numbers from 1 to x can be expressed without any gaps
private static int getSequenceLength(List<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) {
Scanner scanner = new Scanner(System.in);
int numDigits = scanner.nextInt();
List<Double> numbers = new ArrayList<>();
for (int i = 0; i < numDigits; i++) {
numbers.add(scanner.nextDouble());
}
System.out.println(getSequenceLength(numbers));
scanner.close();
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #93: Arithmetic expressions
You are viewing a single comment's thread. Return to all comments →
import java.util.*;
public class LongestSequence { private static final double EPSILON = 0.00001;
}