Avg CTC: 13lpa
Job Roles: Full Stack Developer, Java Developer,
Location: Mumbai, Bengaluru, Chennai, Hyderabad
Job link: Apply here
Click here to Practice
Submit Problem to OJ
Antony builds a monotonically increasing (According to Wikipedia: always increasing, or remaining constant but never decreasing) array(a) of a stack of pebbles; Each element in the array denotes the size of the pebble stack that Akbar built. However, a cheeky youngster named Antony, his younger brother tries to break the pattern. Therefore, instead of directly removing stones from one of the stacks and breaking the pattern he uses the following algorithm on the array a to do it.
Repeat until the array has at least two elements (stacks) and is monotonically increasing:
- Select any two consecutive elements in array
- Find the bitwise XOR of two elements selected
- Remove the two elements and insert the value found in step 2 at their position.
It is important to note that the array size is reduced by one after each iteration and the algorithm stops once the array size becomes 1.
For example, consider array a = [1, 2, 4, 6, 20]
- Antony selects a0 and a1 i.e. 1 and 2
- Finds their bitwise XOR 1 ⊕ 2 = 3
- Remove 1, 2 from the array and insert 3 at their position.
Now the array becomes a = [3, 4, 6, 20]
- Antony selects a0 and a1 i.e. 3 and 4
- Finds their bitwise XOR 3 ⊕ 4 = 7
- Removes 3, and 4 from the array and inserts 7 at their position
Finally, after two iterations array is not monotonically increasing anymore, a = [7, 6, 20].
As Antony has other tasks to complete, he wants to make as few iterations as feasible. Help Anthony find it, or print -1 if it is impossible to do so.
The first line contains the size of the array a single integer n (2 <= n <= 10^5)
The second line consists of n integers a0, a1, a2, ...... an-1 (1 <= ai <= 10^9) the elements of the array. Note that ai <= ai+1 for all 0 <= i < n-1
Return a single integer with the minimum number of iterations required if it is impossible return -1.
1 2 4 6 20
1 2 3
3 4 7 8 8