Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find element at given index after a number of rotations

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.

Not Able to Understand Why starting from last rotation gives right result but if we start from rotation 0 to last in loop it gives wrong result???

https://www.geeksforgeeks.org/find-element-given-index-number-rotations/

// 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 will give right result but following will produce wrong result.

for (int i = 0; i < rotations; 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--;
                }
            }
like image 882
Sanjeev Guglani Avatar asked Jan 03 '23 07:01

Sanjeev Guglani


1 Answers

Lets us consider given 5 length array A1.

You have applied {0,2} rotation on A1. It is changed to A2.
You have applied {0,3} rotation on A2.. It is changed to A3

Now you are looking for output index 1 in A3 (which is {0,3} rotated on A2).
So Index 1 in A3 = Index 0 in A2 (as per the logic)

Now you are looking for Index 0 in A2 (which is {0,2} rotated on A1)
So Index 0 in A2 = Index 2 in A1 (as per the logic)

Hope this explanation clears why the rotations array is iterated in reverse way.

like image 160
Anil Kumar Konam Avatar answered Jan 10 '23 23:01

Anil Kumar Konam