A teacher takes an array of numbers and asks the students to perform the following operation: pick two adjacent positive numbers, ai and ai+1, and replace the two numbers with either (ai%(ai+1)) or (ai+1)%ai ,where x%y denotes x modulo y. Thus, after each operation, the array's length decreases by 1.
The task is to find the minimum possible length of the array, which can be achieved by performing the above operation any number of times
Example
Consider the array's length to be n=4 and the array of numbers to be arr=[1,1,2,3]. The following sequence of operations can be performed (considering 1-based indexing):
- arr=[1, 1, 2, 3]: Choose i=3, thus arr[i]= 2 and arr[i+1]=3. We get the new value to be given by 2%3
=2 or 3 % 2=1. The resulting array can thus be [1, 1, 2] or [1, 1. 1]. We consider the former one to minimize the array length.
- arr=[1,1,2]: Choose i= 2, thus arr[i]=1 and arr[i+1]=2. We can get the new array as [1, 1].
3 arr=[1, 1]: Choose i=1 to get the array [0].
Thus the minimum possible length for the above array would be 1.
Could someone please help me in solving this?
