# Reduce the given Array of [1, N] by rotating left or right based on given conditions

Reduce the given Array of [1, N] by rotating left or right based on given conditionsGiven a sorted array arr[] of the first N Natural Numbers and an integer X, the task is to print the last remaining element after performing the below operations (N – 1) times:Examples:Input: N = 5, arr[] = {1, 2, 3, 4, 5}, X = 1Output: 3Explanation:The operations are performed as follows:Rotating the array right by 1 unit modifies the array to {5, 1, 2, 3, 4}. Deleting the array element modifies the array to {5, 1, 2, 3}.Rotating the array right by 1 unit modifies the array to {3, 5, 1, 2}. Deleting the array element modifies the array to {3, 5, 1}.Rotating the array right by 1 unit modifies the array to {1, 3, 5}. Deleting the array element modifies the array to {1, 3}. Rotating the array right by 1 unit modifies the array to {3, 1}. Deleting the array element modifies the array to {3}.Therefore, the last remaining element is 3.Input: N = 5, arr[] = {1, 2, 3, 4, 5}, X = 2Output: 3Naive Approach: The simplest approach to solve the given problem is to push all the numbers of the range [1, N] in a deque and perform the given operations (N – 1) times according to the given value of X and then print the last remaining element.Time Complexity: O(N2)Auxiliary Space: O(1)Efficient Approach: The given problem can be optimized based on the following observations: If the value of X is 1, then the last left element will be the difference between the smallest power of 2 greater N and N.If the value of X is 2, then the last left element will be 2*(N – D) + 1, where D represents the largest power of 2 less than or equal to N.Follow the steps below to solve the problem:Store the power of 2 greater than N in a variable, say nextPower.If the value of X is 1, then print the value (nextPower – N) as the result.Otherwise, print the value 2*(N – nextPower / 2) + 1 as the result.Below is the implementation of the above approach:C++#include using namespace std; int rotate(int arr[], int N, int X){ long long int nextPower = 1; while (nextPower