Tutorialspoint.dev

Find element at given index after a number of rotations

An array consisting of N integers is given. There are several Right Circular Rotations of range[L..R] that we perform. After performing these rotations, we need to find element at a given index.

Examples :

Input : arr[] : {1, 2, 3, 4, 5}
        ranges[] = { {0, 2}, {0, 3} }
        index : 1
Output : 3
Explanation : After first given rotation {0, 2}
                arr[] = {3, 1, 2, 4, 5}
              After second rotation {0, 3} 
                arr[] = {4, 3, 1, 2, 5}
After all rotations we have element 3 at given
index 1. 



Method : Brute-force The brute force approach is to actually rotate the array for all given ranges, finally return the element in at given index in the modified array.

Method : Efficient We can do offline processing after saving all ranges.
Suppose, our rotate ranges are : [0..2] and [0..3]
We run through these ranges from reverse.

After range [0..3], index 0 will have the element which was on index 3.
So, we can change 0 to 3, i.e. if index = left, index will be changed to right.
After range [0..2], index 3 will remain unaffected.

So, we can make 3 cases :
If index = left, index will be changed to right.
If index is not bounds by the range, no effect of rotation.
If index is in bounds, index will have the element at index-1.

Below is the implementation :

C++

// CPP code to rotate an array
// and answer the index query
#include <bits/stdc++.h>
using namespace std;
  
// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2],
               int rotations, int index)
{
    for (int i = rotations - 1; i >= 0; i--) {
  
        // Range[left...right]
        int left = ranges[i][0];
        int right = ranges[i][1];
  
        // Rotation will not have any effect
        if (left <= index && right >= index) {
            if (index == left)
                index = right;
            else
                index--;
        }
    }
  
    // Returning new element
    return arr[index];
}
  
// Driver
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
  
    // No. of rotations
    int rotations = 2;
  
    // Ranges according to 0-based indexing
    int ranges[rotations][2] = { { 0, 2 }, { 0, 3 } };
  
    int index = 1;
  
    cout << findElement(arr, ranges, rotations, index);
  
    return 0;
  
}

Java

// Java code to rotate an array
// and answer the index query
import java.util.*;
  
class GFG
{
    // Function to compute the element at
    // given index
    static int findElement(int[] arr, int[][] ranges,
                            int rotations, int index)
    {
        for (int i = rotations - 1; i >= 0; i--) {
  
            // Range[left...right]
            int left = ranges[i][0];
            int right = ranges[i][1];
  
            // Rotation will not have any effect
            if (left <= index && right >= index) {
                if (index == left)
                    index = right;
                else
                    index--;
            }
        }
  
        // Returning new element
        return arr[index];
    }
  
    // Driver
    public static void main (String[] args) {
        int[] arr = { 1, 2, 3, 4, 5 };
  
        // No. of rotations
        int rotations = 2;
      
        // Ranges according to 0-based indexing
        int[][] ranges = { { 0, 2 }, { 0, 3 } };
  
        int index = 1;
        System.out.println(findElement(arr, ranges,
                                 rotations, index));
    }
}
  
/* This code is contributed by Mr. Somesh Awasthi */

Python3

# Python 3 code to rotate an array
# and answer the index query
  
# Function to compute the element 
# at given index
def findElement(arr, ranges, rotations, index) :
      
    for i in range(rotations - 1, -1, -1 ) :
      
        # Range[left...right]
        left = ranges[i][0]
        right = ranges[i][1]
  
        # Rotation will not have 
        # any effect
        if (left <= index and right >= index) :
            if (index == left) :
                index = right
            else :
                index = index - 1
          
    # Returning new element
    return arr[index]
  
# Driver Code
arr = [ 1, 2, 3, 4, 5 ]
  
# No. of rotations
rotations = 2
  
# Ranges according to 
# 0-based indexing
ranges = [ [ 0, 2 ], [ 0, 3 ] ]
  
index = 1
  
print(findElement(arr, ranges, rotations, index))
      
# This code is contributed by Nikita Tiwari.

C#

// C# code to rotate an array
// and answer the index query
using System;
  
class GFG
{
    // Function to compute the 
    // element at given index
    static int findElement(int []arr, int [,]ranges,
                           int rotations, int index)
    {
        for (int i = rotations - 1; i >= 0; i--) 
        {
  
            // Range[left...right]
            int left = ranges[i, 0];
            int right = ranges[i, 1];
  
            // Rotation will not 
            // have any effect
            if (left <= index && 
                right >= index)
            {
                if (index == left)
                    index = right;
                else
                    index--;
            }
        }
  
        // Returning new element
        return arr[index];
    }
  
    // Driver Code
    public static void Main () 
    {
        int []arr = { 1, 2, 3, 4, 5 };
  
        // No. of rotations
        int rotations = 2;
      
        // Ranges according 
        // to 0-based indexing
        int [,]ranges = { { 0, 2 }, 
                          { 0, 3 } };
  
        int index = 1;
        Console.Write(findElement(arr, ranges,
                                    rotations, 
                                      index));
    }
}
  
// This code is contributed
// by nitin mittal.

PHP

<?php
// PHP code to rotate an array
// and answer the index query
  
// Function to compute the 
// element at given index
function findElement($arr, $ranges,
                     $rotations, $index)
{
    for ($i = $rotations - 1; 
         $i >= 0; $i--) 
    {
  
        // Range[left...right]
        $left = $ranges[$i][0];
        $right = $ranges[$i][1];
  
        // Rotation will not
        // have any effect
        if ($left <= $index && 
            $right >= $index)
        {
            if ($index == $left)
                $index = $right;
            else
                $index--;
        }
    }
  
    // Returning new element
    return $arr[$index];
}
  
// Driver Code
$arr = array(1, 2, 3, 4, 5);
  
// No. of rotations
$rotations = 2;
  
// Ranges according 
// to 0-based indexing
$ranges = array(array(0, 2),
                array(0, 3));
  
$index = 1;
  
echo findElement($arr, $ranges,
                 $rotations, $index);
  
// This code is contributed by ajit
?>


Output :

3

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter