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

Given 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 = 1
Output: 3
Explanation:
The operations are performed as follows:

  1. 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}.
  2. 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}.
  3. Rotating the array right by 1 unit modifies the array to {1, 3, 5}. Deleting the array element modifies the array to {1, 3}.
  4. 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 = 2
Output: 3

Naive 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(N)
Auxiliary Space: O(1)

Efficient Approach: The given problem can be optimized based on the following observations: 

  1. 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.
  2. 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++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the last element
// left after performing N - 1 queries
// of type X
int rotate(int arr[], int N, int X)
{
    // Stores the next power of 2
    long long int nextPower = 1;
 
    // Iterate until nextPower is at most N
    while (nextPower <= N)
        nextPower *= 2;
 
    // If X is equal to 1
    if (X == 1)
        return nextPower - N;
 
    // Stores the power of 2 less than or
    // equal to N
    long long int prevPower = nextPower / 2;
 
    // Return the final value
    return 2 * (N - prevPower) + 1;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int X = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << rotate(arr, N, X);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to find the last element
// left after performing N - 1 queries
// of type X
static int rotate(int arr[], int N, int X)
{
   
    // Stores the next power of 2
    long nextPower = 1;
 
    // Iterate until nextPower is at most N
    while (nextPower <= N)
        nextPower *= 2;
 
    // If X is equal to 1
    if (X == 1)
        return (int) nextPower - N;
 
    // Stores the power of 2 less than or
    // equal to N
    long prevPower = nextPower / 2;
 
    // Return the final value
    return 2 * (N - (int)prevPower) + 1;
}
 
// Driver Code
    public static void main (String[] args) {
        int arr[] = { 1, 2, 3, 4, 5 };
    int X = 1;
    int N =arr.length;
 
   System.out.println(rotate(arr, N, X));
 
    }
}
 
    // This code is contributed by Potta Lokesh

Python3

# Python3 program for the above approach
 
# Function to find the last element
# left after performing N - 1 queries
# of type X
def rotate(arr, N, X):
    # Stores the next power of 2
    nextPower = 1
 
    # Iterate until nextPower is at most N
    while (nextPower <= N):
        nextPower *= 2
 
    # If X is equal to 1
    if (X == 1):
        ans = nextPower - N
        return ans
 
    # Stores the power of 2 less than or
    # equal to N
    prevPower = nextPower // 2
 
    # Return the final value
    return 2 * (N - prevPower) + 1
 
 
# Driver Code
arr = [1, 2, 3, 4, 5]
X = 1
N = len(arr)
print(rotate(arr, N, X))
 
# This code is contributed by amreshkumar3.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the last element
// left after performing N - 1 queries
// of type X
static int rotate(int []arr, int N, int X)
{
     
    // Stores the next power of 2
    int nextPower = 1;
 
    // Iterate until nextPower is at most N
    while (nextPower <= N)
        nextPower *= 2;
 
    // If X is equal to 1
    if (X == 1)
        return nextPower - N;
 
    // Stores the power of 2 less than or
    // equal to N
    int prevPower = nextPower / 2;
 
    // Return the final value
    return 2 * (N - prevPower) + 1;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 1, 2, 3, 4, 5 };
    int X = 1;
    int N = arr.Length;
 
    Console.Write(rotate(arr, N, X));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
       // JavaScript program for the above approach
 
       // Function to find the last element
       // left after performing N - 1 queries
       // of type X
       function rotate(arr, N, X) {
           // Stores the next power of 2
           let nextPower = 1;
 
           // Iterate until nextPower is at most N
           while (nextPower <= N)
               nextPower *= 2;
 
           // If X is equal to 1
           if (X == 1)
               return nextPower - N;
 
           // Stores the power of 2 less than or
           // equal to N
           let prevPower = nextPower / 2;
 
           // Return the final value
           return 2 * (N - prevPower) + 1;
       }
 
       // Driver Code
       let arr = [1, 2, 3, 4, 5];
       let X = 1;
       let N = arr.length;
 
       document.write(rotate(arr, N, X));
 
   // This code is contributed by Potta Lokesh
 
   </script>

Output

3

Time Complexity: O(log N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Maximize the count of adjacent element pairs with even sum by rearranging the Array Maximize the count of adjacent element pairs with even sum by rearranging the Array
Minimum cost to convert all elements of a K-size subarray to 0 from given Ternary Array with subarray sum as cost Minimum cost to convert all elements of a K-size subarray to 0 from given Ternary Array with subarray sum as cost
Minimum operations required to make all elements of Array less than equal to 0 Minimum operations required to make all elements of Array less than equal to 0
Maximum subarray sum in an array created after repeated concatenation | Set-2 Maximum subarray sum in an array created after repeated concatenation | Set-2
Maximum range length such that A[i] is maximum in given range for all i from [1, N] Maximum range length such that A[i] is maximum in given range for all i from [1, N]

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 8



 

Horje