This question appeared on Scaler CodeX 2.0 dated 06-02-22.

Statement

You are given 'N', the size of array where each element in array is Ai = i for each (1 <= i <= N). We have to exactly 'N-1' operations on this array. In each operation, we delete the last element in the array and move the second last element to the front of the array. After completion of all operations, find the remaining number in the array.

Constraints

1 <= N <= 1e9

Sample Test Case — 1

Input -> N = 5

Output -> 4

Explanation

• Initial Array -> [1, 2, 3, 4, 5]

• Operation 1 -> [4, 1, 2, 3] (Delete 5, then array is [1, 2, 3, 4] and move 4 to front of array getting [4, 1, 2, 3])

• Operation 2 -> [2, 4, 1] (Delete 3, then array is [4, 1, 2] and move 2 to front of array getting [2, 4, 1])

• Operation 3 -> [4, 2]

• Operation 4 -> [4]

Sample Test Case — 2

Input -> N = 6

Output -> 3

Explanation

• Initial Array -> [1, 2, 3, 4, 5, 6]

• Operation 1 -> [5, 1, 2, 3, 4] (Delete 6, then array is [1, 2, 3, 4, 5] and move 5 to front of array getting [5, 1, 2, 3, 4])

• Operation 2 -> [3, 5, 1, 2] (Delete 4, then array is [5, 1, 2, 3] and move 3 to front of array getting [3, 5, 1, 2])

• Operation 3 -> [1, 3, 5]

• Operation 4 -> [3, 1]

• Operation 5 -> [3]

Can anyone solve this problem ???