## Tuesday, October 18, 2016

### Array elements subtraction Game

Imagine you have an array as [2， 7], subtract 2 from 7 and append result to the original array -> [2,7,5]
[2， 7， 5] -> [2， 7， 5，3]
[2，7，5，3] -> [2，7，5，3，1] or [2，7，5，3，4]
[2，7，5，3，1] -〉[2，7，5，3，1， 6] or [2，7，5，3，1， 4]
[2，7，5，3，1， 4] ->[2，7，5，3，1， 6， 4] or [2，7，5，3，1，4，6]
[2，7，5，3，4] -〉 [2，7，5，3，4，1] -〉[2，7，5，3，4，1，6]
Subtract between elements in the array until you cannot do so( no new element generated), The bold one are final results
The question is to ask you output all the results in List<List<res>> format

Little follow-up: Instead of a list of all possible orders, just return a list of all reachable numbers. Can you do it in one line?
My idea is to fine Greatest Common Divisor and fill from 1 * GCD , 2* GCD, 3 * GCD ...... Max(arr).
``````       static List<int> cal(int[] arr) {

Func<int, int, int> gcd = null;

gcd = (a, b) => b == 0 ? a : gcd(b, a % b);

int gcdNO = arr.Aggregate(gcd);

return Enumerable.Range(1, arr.Max() / gcdNO).Select(x => x * gcdNO).ToList();
}``````
``irb(main):005:0> def numbers(a) (0..a.max).step(a[0].gcd(a[1])).to_a[1..-1] end``
``````public Iterable<Integer> getReachableNums(int[] arr){
List<Integer> res = new ArrayList<Integer>();
assert(arr.length == 2);

int gcd = gcd(arr[0], arr[1]);
int max = Math.max(arr[0], arr[1]);
for (int i = 1; i*gcd <= max; i++){
}

return res;
}

private int gcd(int a, int b){
if (a * b == 0){
return 1;
} else if (a == b){
return a;
} else {
a = (a < b) ? a : a + b;
b = (b > a) ? b : a - b;
a = (a > b) ? a - b : a;
return gcd(a, b - a);
}
}``````