BNY Mellon OA-2 2023
Problem Description
Lily is guiding a group of young students for an upcoming Mathematics Challenge in honor of Women's Day. In one of her lessons, she decides to teach the students about modulo arithmetic.
She takes an array of numbers and asks the girls to perform the following operation: pick two adjacent positive numbers (a_j) and (a_j+1), and replace the two numbers with either (a_j % a_j+1) or (a_j+1 % a_j), where (x % y) denotes (x) modulo (y). Thus, after each operation, the length of the array decreases by 1.
Lily asks the girls to find the minimum possible length of the array which can be achieved by performing the above operation any number of times.
Input Format
- The first line contains a single integer (n), the length of the array.
- The second line contains (n) space-separated integers, the elements of the array.
Output Format
- An integer denoting the minimum possible length of the array.
Constraints
- 1 <= n <= 10^5
- 1 <= a[i] <= 10^9
Example
Consider the length of the array 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 minimise 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]).
- (arr = [1, 1]): Choose (i = 1) to get the array ([0]).
Thus the minimum possible length for the above array would be 1.