Hackwithinfy question! help please!

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!

I think ans will be max element of array unless array length is 1

@totally_an_alt Please Share The Link Of The Question

No check for case of 2,6 u can get 2,4,6 after infinite steps

I guess the answer would range from gcd of the whole array to all its multiples until the max element.

3 Likes

I think the same way.