I am doing the following programming exercise: Is my friend cheating?. The statement is:
A friend of mine takes a sequence of numbers from 1 to n (where n > 0). Within that sequence, he chooses two numbers, a and b. He says that the product of a and b should be equal to the sum of all numbers in the sequence, excluding a and b. Given a number n, could you tell me the numbers he excluded from the sequence?
The function takes the parameter: n (n is always strictly greater than 0) and returns an array or a string (depending on the language) of the form:
[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or or [{a, b}, ...]
with all (a, b) which are the possible removed numbers in the sequence 1 to n.
[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or ...will be sorted in increasing order of the "a".
It happens that there are several possible (a, b). The function returns an empty array (or an empty string) if no possible numbers are found which will prove that my friend has not told the truth! (Go: in this case return nil).
Examples:
removeNb(26) should return [[15, 21], [21, 15]]
The idea was:
Calculate sum of 1..n
For each number a
For each number b
if a*b=sum-(a+b)
add to result
And I have written the following code:
import java.util.*;
import java.util.stream.*;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
System.out.println("n: "+n);
long sum = LongStream.rangeClosed(1,n).sum();
List<long[]> result = new ArrayList<>();
System.out.println("sum: "+sum);
for(int a = 1; a <= n && a <= sum; a++){
System.out.println("a: "+a);
long prodMax = a*n;
long sumMax = sum-(a+n);
if(prodMax < sumMax){
System.out.println("prodMax: "+prodMax);
System.out.println("sumMax: "+sumMax);
continue;
};
for(int b = 1; b <= n && a*b <= (sum-(a+b)); b++){
if(a==b) continue;
System.out.println("b: "+b);
if(a*b == sum-(a+b)){
result.add(new long[]{a,b});
System.out.println("result: "+Arrays.deepToString(result.toArray()));
}
}
}
System.out.println("result: "+Arrays.deepToString(result.toArray()));
return result;
}
}
It passes the following tests:
import static org.junit.Assert.*;
import java.util.List;
import java.util.ArrayList;
import org.junit.Test;
public class RemovedNumbersTest {
@Test
public void test12() {
List<long[]> res = new ArrayList<long[]>();
res.add(new long[] {15, 21});
res.add(new long[] {21, 15});
List<long[]> a = RemovedNumbers.removNb(26);
assertArrayEquals(res.get(0), a.get(0));
assertArrayEquals(res.get(1), a.get(1));
}
@Test
public void test14() {
List<long[]> res = new ArrayList<long[]>();
List<long[]> a = RemovedNumbers.removNb(100);
assertTrue(res.size() == a.size());
}
}
For example for test12, the trace is:
n: 26
sum: 351
a: 1
prodMax: 26
sumMax: 324
a: 2
prodMax: 52
sumMax: 323
a: 3
prodMax: 78
sumMax: 322
a: 4
prodMax: 104
sumMax: 321
a: 5
prodMax: 130
sumMax: 320
a: 6
prodMax: 156
sumMax: 319
a: 7
prodMax: 182
sumMax: 318
a: 8
prodMax: 208
sumMax: 317
a: 9
prodMax: 234
sumMax: 316
a: 10
prodMax: 260
sumMax: 315
a: 11
prodMax: 286
sumMax: 314
a: 12
prodMax: 312
sumMax: 313
a: 13
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 14
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
b: 23
b: 24
a: 14
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
a: 15
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
result: [[15, 21]]
a: 16
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 17
b: 18
b: 19
a: 17
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 18
a: 18
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 17
a: 19
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
a: 20
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
a: 21
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
result: [[15, 21], [21, 15]]
a: 22
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
a: 23
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 24
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 25
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
a: 26
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
result: [[15, 21], [21, 15]]
However when the input is a big number, for example n=1000003, it times out (execution time is bigger than 16000ms).
I have also read:
How could we improve this algorithm?
