Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Algorithm
4.1.
Method 1
4.2.
Method 2
5.
Working
6.
Implementation
6.1.
Approach 1 (C++)
6.1.1.
Code
6.1.2.
Output
6.2.
Approach 2 (Python 3)
6.2.1.
Code
6.2.2.
Output
6.3.
Approach 3 (C#)
6.3.1.
Code
6.3.2.
Output
7.
Frequently Asked Questions
7.1.
Is it possible to modify the size of an array during execution?
7.2.
What do you mean by rotation of an array?
7.3.
What do you mean by circular right rotation?
7.4.
What is the time complexity of Circular right rotation?
8.
Conclusion
Last Updated: Mar 27, 2024

Find Element at Given Index After Several Rotations

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

We all know that accessing an array element is the same as indexing an array. We can use the index number of an array element to access it.

However, do you know what happens when we perform circular rotations on given ranges [L…….R]. How to find an element at a given index after several rotations?

                                                   

                                                                            Source

Let us learn about finding an element at a given index after a number of rotations to answer this question.

Problem Statement

Consider an n-dimensional integer array with ranges indicating the left and right ranges for rotating the array clockwise. After performing the rotation, find the element at a given index.

So, firstly we need to circular right rotate the given array for the given ranges. After performing all the rotations, find the element at the given position in the final array.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Here is an example of understanding the problem of finding an element at a given index after several rotations.

Input:

array = {1, 5, 3, 4, 8},

rotations = {{0, 2}, {1, 3}, {0, 4}}, and 

index = 2

Output:

Element at index two after rotations is: 4

Explanation:

After {0, 2}, the array will become {3, 1, 5, 4, 8}

After {1, 3}, the array will become {3, 4, 1, 5, 8}

After {0, 4},  the array will become {8, 3, 4, 1, 5}

Now,  we have the element at index 2 is 4.

Also see,  Euclid GCD Algorithm

Algorithm

It's time to learn the Methods to find the element. We will see the algorithms as solutions to our problem. Why wait? Let’s together learn something new.

                                                

                                                                                      Source

Method 1

The very first method is the Brute-force method. This algorithm consists of the following steps:

  • Properly rotate the array for all specified ranges.
  • Then return the element in the updated array at the given index.

Method 2

We can analyse the supplied set of ranges without rotating the array instead of executing all of the rotations and locating the member at the given index. It consists of the following processes:

  • Iterate through all the sets of ranges in reverse order(from last to first).
  • If the index is larger than left and lower than right;
  • If yes, see if the index is equal to the left; move the index to the right.
    Otherwise, decrement the index.
  • At the index position, print the array element.

Working

Till now, we have learned examples and algorithms. But how are these algorithms working? What is happening precisely in these algorithms?

                                             

                                                                     Source

To answer all these questions, let’s understand the working of index-based(Method 2)  algorithms in detail.

  • Given Array: arr = {1, 5, 3, 4, 8}
  • Given Rotations: { (0, 2), (1, 3), (0,4) }
  • Index = 2
  1. Range (0, 4) and index = 2.
    Since, Left range < = Index < = Right Range and Index ! = 0.
    Decrement Index.
    Now Index = 1.
     
  2. Range (1, 3) and index = 1.
    Since, Left range  = Index.
    Set Index to Right Range Value.
    Now Index = 3.
     
  3. Range (0, 2) and index = 3.
    Since the Index is not inbound.
    Do nothing.

So the new index is three, and our output is 4.

Now, let’s verify the result with the brute-force method:

  1. First Rotation: (0, 2)
    Updated array: arr={ 3, 1, 5, 4, 8}
     
  2. Second Rotation: (1, 3)
    Updated array: arr={ 3, 4, 1, 5, 8}
     
  3. Third Rotation: (0, 4)
    Updated array: arr={ 8, 3, 4, 1, 5}

So the element at index 2 is 4, which is the same as the previous step. This is the reason that we process the ranges in reverse order

Implementation

Here is the implementation of an effective solution to the problem in different languages.

Approach 1 (C++)

The given code is the implementation of our algorithm in C++ language.

Code

#include <bits/stdc++.h>
using namespace std;
// Function to perform rotations and find index element
int Element(int arr[], int ranges[][2],
    int rotations, int index)
{
    for (int i = rotations - 1; i >= 0; i--) {
        int left = ranges[i][0];
        int right = ranges[i][1];

        // checking left and right condition
        if (left <= index && right >= index) {
            if (index == left)
                index = right;
            else
                index--;
        }
    }

    // Returning the new element
    return arr[index];
}

// Main function
int main()
{
    int arr[100], n, element;
    
    cout << "Enter the Number of elements: ";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Enter the element " << i + 1 << ": ";
        cin >> arr[i];
    }
    int rotations;
    cout << "Enter the number of rotations: ";
    cin >> rotations;

    int ranges[rotations][2];
    for (int i = 0; i < rotations; i++) {
        cout << "For Rotation " << i + 1 << endl;
        cout << "Enter left Range: ";
        cin >> ranges[i][0];
        cout << "Enter right Range: ";
        cin >> ranges[i][1];
    }
    int index;
    cout << "Enter the index: ";
    cin >> index;
    cout << "Element at the index " << index << " after all the rotations is: " << Element(arr, ranges, rotations, index);
    return 0;
}

Output

Approach 2 (Python 3)

The given code is the implementation of our algorithm using the Python language.

Code

# Function to find the element
def Element(arr, ranges, rotations, index) :

	for i in range(rotations - 1, -1, -1 ) :
	
		# Ranges
		left = ranges[i][0]
		right = ranges[i][1]
		if (left <= index and right >= index) :
			if (index == left) :
					index = right
			else :
					index = index - 1
		# Returning the new element
		return arr[index]

	# Driver Code
	arr = [ 1, 5, 3, 4, 8 ]
	# No. of rotations
	rotations = 3
	# Ranges according to
	# 0-based indexing
	ranges = [ [ 0, 2 ], [ 1, 3 ], [ 0, 4 ]]
	index = 2
	print("The element at given index:", Element(arr, ranges, rotations, index))

Output

Approach 3 (C#)

The given code is the implementation of our algorithm using the C# language.

Code

using System;
class Array
{
	// Function to find the element
	static int Element(int []arr, int [,]ranges, int rotations, int index)
	{
		for (int i = rotations - 1; i >= 0; i--)
		{
		// Range
		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, 5, 3, 4, 8 };

	// The No. of rotations
	int rotations = 3;

	// Ranges 
	int [,]ranges = { { 0, 2 },
	{ 1, 3 }, { 0, 4 } };
	int index = 2;
	Console.Write("The element at given index is:" +Element(arr, ranges, rotations,  index));
}
}

Output

Check out this problem - First And Last Occurrences Of X

Frequently Asked Questions

Is it possible to modify the size of an array during execution?

No, we won't be able to adjust the array size. There are, however, similar data types that allow for size changes.

What do you mean by rotation of an array?

Array rotation implies moving the array elements to the left or right by a specified amount. An array can be rotated to the provided number of positions to the left (clockwise) or right (anti-clockwise).

What do you mean by circular right rotation?

When all items of an array are moved one position to the right, the array is said to be right rotated.

What is the time complexity of Circular right rotation?

The time complexity of Circular right rotation is O(n), where n is the number of elements in the given array.

Conclusion

This blog discussed finding an element at a given index after several rotations.

We have discussed,

  • Example of finding the element.
  • Algorithm to find the element using brute-force method and then using index method.
  • Working of the Algorithm.
  • Implementation of the Algorithm.

This blog is related to array rotation, so it is advised to check these articles on Rotation Count and Circular right rotation.  You can learn the Block Swap algorithm for Array Rotation.

To learn more about array rotation, visit the Array Rotation Section at Coding Ninjas Studio.

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!

 

We wish you Good Luck! Keep coding and keep reading Ninja!!

Live masterclass