Перетасуйте колоду карт и ответьте на вопрос

Опубликовано: 19 Января, 2022

Учитывая колоду из 2 ^ N карт (0… 2 ^ N - 1), перемешайте ее за N шагов. На шаге k (0 <k <N) мы делим колоду на 2k колод одинакового размера. Каждая из этих колод переупорядочивается: сначала все карты, лежащие на четных позициях, затем все карты, лежащие на нечетных позициях (порядок сохраняется в каждой из двух подпоследовательностей). Теперь нам дан ключ (индекс). Мы должны ответить карточке на этой позиции (индексация на основе 0).
Примеры:

 Ввод: N = 3 (размер = 2 ^ N), ключ = 3
Выход: 6
Объяснение : 
Пакет: 0 1 2 3 4 5 6 7
Перемешать 1: 0 2 4 6 | 1 3 5 7
Перемешать 2: 0 4 | 2 6 | 1 5 | 3 7
Карточка с индексом 3: 6

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Method 1: We can simply simulate the whole process and find the exact order of the cards after all the N shuffles are done. 
Time Complexity: O(N * 2^N)
Method 2 : 
Let us try to find the binary representation of Key and the final answer and try to spot some observations based on it.
Let N = 3
Below is the table :
Key ANS 
000 000 
001 100 
010 010 
011 110 
100 001 
101 101 
110 011 
111 111
It is clearly visible that the answer is the reverse of a binary representation of Key. 
 

C++

// 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

// 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

# 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#

// 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.

Javascript

<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>

Выход:

 6

Эта статья предоставлена Rohit . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.