Baraja un paquete de cartas y responde la consulta.

Dado un paquete de 2^N cartas (0 … 2^N – 1), barájalo en N pasos. En el paso k (0 < k < N) dividimos el mazo en 2k mazos del mismo tamaño. Cada uno de esos mazos se reordena teniendo primero todas las cartas que están en posiciones pares, seguidas de todas las cartas que están en posiciones impares (el orden se conserva en cada una de las dos subsecuencias). Ahora, se nos da una clave (índice). Tenemos que contestar la tarjeta en esa posición (indexación basada en 0).
Ejemplos: 
 

Input : N = 3 (Size = 2^N), Key = 3
Output : 6
Explanation : 
Pack :      0 1 2 3 4 5 6 7
Shuffle 1 : 0 2 4 6|1 3 5 7
Shuffle 2 : 0 4|2 6|1 5|3 7
Card at index 3 : 6

Método 1: podemos simplemente simular todo el proceso y encontrar el orden exacto de las cartas después de que se hayan hecho todos los N barajes. 
Complejidad de tiempo: O(N * 2^N)
Método 2: 
Tratemos de encontrar la representación binaria de Key y la respuesta final e intentemos detectar algunas observaciones basadas en ella.
Sea N = 3
A continuación se muestra la tabla:
Key ANS 
000 000 
001 100 
010 010 
011 110 
100 001 
101 101 
110 011 
111 111
Es claramente visible que la respuesta es la inversa de una representación binaria de Key. 
 

// C++ program to find the card at given index
// after N shuffles
#include <bits/stdc++.h>
using namespace std;
 
// function to find card at given index
void shuffle(int N, int key)
{
 
    // Answer will be reversal of N bits from MSB
    unsigned int NO_OF_BITS = N;
    unsigned int reverse_num = 0, temp;
 
    // Calculating the reverse binary representation
    for (int i = 0; i < NO_OF_BITS; i++) {
        temp = (key & (1 << i));
        if (temp)
            reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
    }
 
    // Printing the result
    cout << reverse_num;
}
 
// driver code
int main()
{
    // No. of Shuffle Steps
    int N = 3;
 
    // Key position
    unsigned int key = 3;
 
    shuffle(N, key);
    return 0;
}

// Java program to find the card at given index
// after N shuffles
class GFG {
     
    // function to find card at given index
    static void shuffle(int N, int key)
    {
     
        // Answer will be reversal of N bits from MSB
        int NO_OF_BITS = N;
        int reverse_num = 0, temp;
     
        // Calculating the reverse binary representation
        for (int i = 0; i < NO_OF_BITS; i++) {
            temp = (key & (1 << i));
            if (temp>0)
                reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
        }
     
        // Printing the result
        System.out.print(reverse_num);
    }
     
    //Driver code
    public static void main (String[] args)
    {
         
        // No. of Shuffle Steps
        int N = 3;
     
        // Key position
        int key = 3;
     
        shuffle(N, key);
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find the card
# at given index after N shuffles
 
# Function to find card at given index
def shuffle(N, key):
 
    # Answer will be reversal
    # of N bits from MSB
    NO_OF_BITS = N
    reverse_num = 0
 
    # Calculating the reverse binary representation
    for i in range(NO_OF_BITS):
        temp = (key & (1 << i))
        if (temp):
            reverse_num |= (1 << ((NO_OF_BITS - 1) - i))
     
    # Printing the result
    print(reverse_num)
 
# Driver code
 
# No. of Shuffle Steps
N = 3
 
# Key position
key = 3
shuffle(N, key)
 
# This code is contributed by Anant Agarwal.

// C# program to find the card at given index
// after N shuffles
using System;
 
class GFG {
     
    // function to find card at given index
    static void shuffle(int N, int key)
    {
      
        // Answer will be reversal of N bits from MSB
        int NO_OF_BITS = N;
        int reverse_num = 0, temp;
      
        // Calculating the reverse binary representation
        for (int i = 0; i < NO_OF_BITS; i++) {
            temp = (key & (1 << i));
            if (temp > 0)
                reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
        }
      
        // Printing the result
        Console.Write(reverse_num);
    }
     
    //Driver code
    public static void Main()
    {
         
        // No. of Shuffle Steps
        int N = 3;
     
        // Key position
        int key = 3;
     
        shuffle(N, key);
    }
}
 
// This code is contributed by Anant Agarwal.

<script>
 
// Javascript program to find the card at given index
// after N shuffles
 
    // function to find card at given index
    function shuffle(N, key)
    {
     
        // Answer will be reversal of N bits from MSB
        let NO_OF_BITS = N;
        let reverse_num = 0, temp;
     
        // Calculating the reverse binary representation
        for (let i = 0; i < NO_OF_BITS; i++) {
            temp = (key & (1 << i));
            if (temp>0)
                reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
        }
     
        // Printing the result
        document.write(reverse_num);
    }
     
 
// driver program
 
        // No. of Shuffle Steps
        let N = 3;
     
        // Key position
        let key = 3;
     
        shuffle(N, key);
         
</script>

Producción:  

6

Complejidad del tiempo – O(n)

Complejidad espacial – O(1)

Este artículo es una contribución de Rohit . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.