BNY Mellon OA 2023 - Women's Day Mathematics Challenge
Claire is mentoring a group of students to participate in the upcoming Women's Day Mathematics Challenge. In one of her classes, she plans to teach modulo arithmetic to the girls.
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.
Claire 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.