You are given an array of length N. In one move you can take any two elements of the array and add the absolute difference of those elements back to the array.
Count the number of distinct elements the array can contain after infinite number of moves.
Constraints
1 <= N <= 10^5
1 <= A[i] <= 10^9
Sample input:
3
2 6 5
Sample output:
6
Explaination:
Take 2 and 6, abs(2 - 6) = 4, array becomes [2, 6, 5, 4]
Take 6 and 5, abs(6 - 5) = 1, array becomes [2, 6, 5, 4, 1]
Take 2 and 5, abs(2 - 5) = 3, array becomes [2, 6, 5, 4, 1, 3]
Note that if you take any two element then absolute difference of them is already present in the array. So number of elements will be 6.
Iām trying to solve this problem from last two days but I cannot get a solution better than the brute force. please help me!