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?
UPD: Solution invalid, see replies
what if the array elements are [2,2,2,2]. After the operations, we end up getting [0,0]. So in this case the answer is 2. One thing to be noted is that we can perform the operations only with positive number pairs (as mentioned in the question). Considering this, would be please explain the solution again?
I believe I have a solution which works in O(n) time.
Let m be the smallest number in the array. First, consider the case when there is only one m. In this case, it is very easy to see how to remove all other numbers: you simply always choose a pair that contains m and some other number b and replace it with m % b = m (since b > m).
Second, what do we do when there are multiple minimums? We try to somehow get an integer that is less than m. If we manage to do that, we confidently print '1', because of the reasons stated above. Turns out, we can do that if and only if there is a number somewhere in the array that is not a multiple of m. I believe it is best to show the idea on an example.
Consider a = [6, 3, 3, 3, 6, 9, 11, 12]. In this case m = 3, and every other number is a multiple of m, except for a[7] = 11. Once we found an a[i] such that a[i] % m != 0, we can remove 6 and 9 using the same trick, and we will have a = [6, 3, 3, 3, 11, 12]. Notice that a % b < b. So we replace [3, 11] with 11 % 3 = 2 < 3 and have a = [6, 3, 3, 2, 12]. Obviously, after some operations we will be able to reduce the length to 1 (a = [2])
If all of the numbers are multiples of m, then we can't perform any sequence of operations that creates a number less than m (not counting zeros). So we just erase all numbers greater than m and turn as many pairs as we can to zeros. For example, if a = [6, 3, 3, 3, 6, 9, 12, 12], then we can make a = [3, 3, 3], and then a = [0, 3]. The answer is 2.
To recap:
Thanks a lot for the solution. Also the first line of the problem says that pick two adjacent 'positive numbers'. So we exclude zeros in operations.
Oh, sorry, my bad :)
In case of $$$a = [6, 3, 3, 3, 6, 9, 11, 12]$$$ we can choose firstly last pair $$$[11, 12]$$$ and then replace it with $$$1 = 12 \% 11$$$. Now, when we have $$$1$$$ in the array, we can eliminate all other elements because $$$1 \% a_i = 1$$$ if $$$a_i \gt 1$$$. So the answer should be $$$1$$$.
The case in which a = [6, 3, 3, 3, 6, 9, 11, 12] was handled one paragraph earlier. The answer would be 2 if a = [6, 3, 3, 3, 6, 9, 12, 12].
IMO Solution is Correct. Can you tell on which test case it fails ?
not fail I think he miss read the first line of the problem
i think to do modulo you use %