Consider a shuffle game. There are 3 glasses numbered from 1 to 3 and one ball is hidden under any one of the glass. Then any 2 of the glasses are shuffled. This operation is made 3 times.
Given an integer N ranged [1, 3] and 3 pairs of integers of the same range. The N-th glass contain the ball initially and every pair of the given integers represents the indices of the glasses needs to be shuffled. Remember the glasses are renumbered after each shuffle.
The task is to find out the index of the glass which contains the ball after all the shuffle operation.
Examples:Â
Â
Input:Â
N = 3Â
3 1Â
2 1Â
1 2Â
Output: 1Â
Firstly the 3rd glass contain the ball.Â
After the first shuffle operation (3, 1), 1st glass contain the ball.Â
After the second shuffle operation (2, 1), 2nd glass contain the ball.Â
After the third shuffle operation (1, 2), 1st glass contain the ball.
Input:Â
N = 1Â
1 3Â
1 2Â
2 3Â
Output: 2Â
Â
Â
Approach: The simplest approach will be to run a loop for every shuffle operation.Â
If any of the 2 glasses being shuffled contain the ball then it is obvious to change the value of N to the index of the glass being shuffled with.Â
If any of the 2 shuffling glasses doesn’t contain the ball, then nothing needs to be done.
Below is the implementation of the above code:Â
Â
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;Â
const int M = 3, N = 2;Â
// Function to generate the index of the glass// containing the ballvoid getIndex(int n, int shuffle[][N]){Â Â Â Â for (int i = 0; i < 3; i++) {Â
        // Checking if the glasses        // being shuffled contain        // the ballÂ
        // Change the index        if (shuffle[i][0] == n)            n = shuffle[i][1];Â
        // Change the index        else if (shuffle[i][1] == n)            n = shuffle[i][0];    }Â
    // Print the index    cout << n;}Â
// Driver's Codeint main(){Â Â Â Â int n = 3;Â
    // Storing all the shuffle operation    int shuffle[M][N] = {        { 3, 1 },        { 2, 1 },        { 1, 2 }    };Â
    getIndex(n, shuffle);} |
Java
// Java implementation of the above approachimport java.io.*;Â
class GFG{static int M = 3;static int N = 2;Â
// Function to generate the index of the glass// containing the ballstatic void getIndex(int n, int shuffle[][]){Â Â Â Â for (int i = 0; i < 3; i++) Â Â Â Â {Â
        // Checking if the glasses        // being shuffled contain        // the ballÂ
        // Change the index        if (shuffle[i][0] == n)            n = shuffle[i][1];Â
        // Change the index        else if (shuffle[i][1] == n)            n = shuffle[i][0];    }Â
    // Print the index    System.out.println (n);}Â
// Driver Codepublic static void main (String[] args) {    int n = 3;         // Storing all the shuffle operation    int shuffle[][] = {{ 3, 1 },                       { 2, 1 },                       { 1, 2 }};         getIndex(n, shuffle);}}Â
// This code is contributed by ajit. |
Python3
# Python3 implementation of # the above approach M = 3; N = 2; Â
# Function to generate the index of# the glass containing the ball def getIndex(n, shuffle) :Â
    for i in range(3) :Â
        # Checking if the glasses         # being shuffled contain         # the ball Â
        # Change the index         if (shuffle[i][0] == n) :            n = shuffle[i][1]; Â
        # Change the index         elif (shuffle[i][1] == n) :            n = shuffle[i][0];Â
    # Print the index     print(n); Â
# Driver Code if __name__ == "__main__" : Â
    n = 3; Â
    # Storing all the shuffle operation     shuffle = [[ 3, 1 ],                [ 2, 1 ],                [ 1, 2 ]]; Â
    getIndex(n, shuffle); Â
# This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approachusing System;Â Â Â Â Â class GFG{static int M = 3;static int N = 2;Â
// Function to generate the index of// the glass containing the ballstatic void getIndex(int n, int [,]shuffle){Â Â Â Â for (int i = 0; i < 3; i++) Â Â Â Â {Â
        // Checking if the glasses        // being shuffled contain        // the ballÂ
        // Change the index        if (shuffle[i, 0] == n)            n = shuffle[i, 1];Â
        // Change the index        else if (shuffle[i, 1] == n)            n = shuffle[i, 0];    }Â
    // Print the index    Console.WriteLine(n);}Â
// Driver Codepublic static void Main (String[] args) {    int n = 3;         // Storing all the shuffle operation    int [,]shuffle = {{ 3, 1 },                      { 2, 1 },                       { 1, 2 }};         getIndex(n, shuffle);}}     // This code is contributed by Princi Singh |
Javascript
<script>// javascript implementation of the above approach     M = 3;     N = 2;Â
    // Function to generate the index of the glass    // containing the ball    function getIndex(n , shuffle) {        for (i = 0; i < 3; i++) {Â
            // Checking if the glasses            // being shuffled contain            // the ballÂ
            // Change the index            if (shuffle[i][0] == n)                n = shuffle[i][1];Â
            // Change the index            else if (shuffle[i][1] == n)                n = shuffle[i][0];        }Â
        // Print the index        document.write(n);    }Â
    // Driver Code             var n = 3;Â
        // Storing all the shuffle operation        var shuffle = [ [ 3, 1 ],                         [ 2, 1 ],                         [ 1, 2 ] ];Â
        getIndex(n, shuffle);Â
// This code contributed by gauravrajput1</script> |
Output:Â
1
Â
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
