Перетасуйте колоду карт и ответьте на вопрос
Учитывая колоду из 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
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.