javaspring7
BAN USER- 0of 0 votes
AnswersImplement Two Sum Interface -
- javaspring7 in United Statespublic interface TwoSum { /** * Stores @param input in an internal data structure. */ void store(int input); /** * Returns true if there is any pair of numbers in the internal data structure which * have sum @param val, and false otherwise. * For example, if the numbers 1, -2, 3, and 6 had been stored, * the method should return true for 4, -1, and 9, but false for 10, 5, and 0 */ boolean test(int val); }
| Report Duplicate | Flag | PURGE
Linkedin Algorithm
This solution is based on eratosthene's sieve. Algorithm is this
-Find all primes upto SQRT(1billion) using sieve.
-check divisibility of numbers starting after 1 billion with all the primes calculated above until 5 primes are found.
It ran in about 20 ms on my laptop.
**Edit - I ran the brute force solution and it is faster than the sieve method. I guess it is because brute force does not need any storage.
public static void find5PrimesfromN() {
long IN = 1000000000l;
int N = (int)Math.sqrt(IN)+1;
boolean[] nonprime = new boolean[N];
int d=2;
while(d < (int)Math.sqrt(N)+1) {
for(int i=d+1; i<=N; i++) {
//System.out.println("compare");
if(i%d == 0) {
nonprime[i-1] = true;
}
}
d++;
for(int k=d; k<N; k++) {
if(!nonprime[k-1]) {
d = k;
break;
}
}
}
List<Integer> primesUpSqRoot = new ArrayList<>();
for(int k=2; k<N; k++) {
if(!nonprime[k-1]) {
primesUpSqRoot.add(k);
}
}
long p = IN+1;
int np = 0;
while(np < 5) {
boolean isP = true;
for(int div : primesUpSqRoot) {
if(p%div == 0) {
isP = false;
break;
}
}
if(isP) {
System.out.println("prime "+p);
np++;
}
p++;
}
}
Iterative solution-
- javaspring7 April 20, 2015