Создайте массив, используя заданные побитовые операции AND, OR и XOR.
Даны побитовые операции И , ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ для N элементов массива, обозначенного как a, b, c. Задача - найти элементы массива. Если такого массива не существует, выведите «-1».
Примеры:
Input: N = 3, a = 4, b = 6, c = 6.
Output: {4, 4, 6}
Explanation:
Bitwise AND of array = 4 & 4 & 6 = 4
Bitwise OR of array = 4 | 4 | 6 = 6
Bitwise XOR of array = 4 ^ 4 ^ 6 = 6
Input: N = 2, a = 4, b = 6, c = 6.
Output: -1
Подход:
- Для побитового И , если i- й бит установлен в a , то в массиве для каждого элемента должен быть установлен i- й бит, потому что если даже один элемент i- й бит равен 0, то побитовое И массива приведет к тому, что i- й бит будет равен 0 .
- Во-вторых, если i- й бит не установлен в a, то значения OR и XOR необходимо обрабатывать одновременно. Если i- й бит установлен в b , то хотя бы в одном элементе должен быть установлен i- й бит. Итак, установите i- й бит в единственный первый элемент массива.
- Теперь, если i- й бит был установлен в b, то i- й бит должен быть проверен в c . Если этот бит установлен в c, то проблем нет, поскольку i- й бит первого элемента уже установлен, поэтому 1 ^ 0 = 1. Если этот бит не установлен в c, установите i- й бит второго элемента. Теперь в b не будет никакого эффекта, а для c 1 ^ 1 будет 0 .
- Затем просто вычислите побитовое И, ИЛИ и XOR массива, чтобы проверить, равно оно или нет. Если результаты не равны, то массив невозможен, иначе ответом будет данный массив.
Ниже представлена реализация подхода:
C ++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the array void findArray( int n, int a, int b, int c) { int arr[n + 1] = {}; // Loop through all bits in number for ( int bit = 30; bit >= 0; bit--) { // If bit is set in AND // then set it in every element // of the array int set = a & (1 << bit); if (set) { for ( int i = 0; i < n; i++) arr[i] |= set; } // If bit is not set in AND else { // But set in b(OR) if (b & (1 << bit)) { // Set bit position // in first element arr[0] |= (1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if (!(c & (1 << bit))) { arr[1] |= (1 << bit); } } } } int aa = INT_MAX, bb = 0, cc = 0; // Calculate AND, OR // and XOR of array for ( int i = 0; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // If not, then array // is not possible else cout << "-1" ; } // Driver Code int main() { // Given Bitwise AND, OR, and XOR int n = 3, a = 4, b = 6, c = 6; // Function Call findArray(n, a, b, c); return 0; } |
Джава
// Java program for the above approach import java.io.*; class GFG{ // Function to find the array static void findArray( int n, int a, int b, int c) { int arr[] = new int [n + 1 ]; // Loop through all bits in number for ( int bit = 30 ; bit >= 0 ; bit--) { // If bit is set in AND // then set it in every element // of the array int set = a & ( 1 << bit); if (set != 0 ) { for ( int i = 0 ; i < n; i++) arr[i] |= set; } // If bit is not set in AND else { // But set in b(OR) if ((b & ( 1 << bit)) != 0 ) { // Set bit position // in first element arr[ 0 ] |= ( 1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if ((c & ( 1 << bit)) == 0 ) { arr[ 1 ] |= ( 1 << bit); } } } } int aa = Integer.MAX_VALUE, bb = 0 , cc = 0 ; // Calculate AND, OR // and XOR of array for ( int i = 0 ; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // If not, then array // is not possible else System.out.println( "-1" ); } // Driver code public static void main(String[] args) { // Given Bitwise AND, OR, and XOR int n = 3 , a = 4 , b = 6 , c = 6 ; // Function Call findArray(n, a, b, c); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for # the above approach import sys # Function to find the array def findArray(n, a, b, c): arr = [ 0 ] * (n + 1 ) # Loop through all bits in number for bit in range ( 30 , - 1 , - 1 ): # If bit is set in AND # then set it in every element # of the array set = a & ( 1 << bit) if ( set ): for i in range (n): arr[i] | = set # If bit is not set in AND else : # But set in b(OR) if (b & ( 1 << bit)): # Set bit position # in first element arr[ 0 ] | = ( 1 << bit) # If bit is not set in c # then set it in second # element to keep xor as # zero for bit position if ( not (c & ( 1 << bit))): arr[ 1 ] | = ( 1 << bit) aa = sys.maxsize bb = 0 cc = 0 # Calculate AND, OR # and XOR of array for i in range (n): aa & = arr[i] bb | = arr[i] cc ^ = arr[i] # Check if values are equal or not if (a = = aa and b = = bb and c = = cc): for i in range (n): print (arr[i], end = " " ) # If not, then array # is not possible else : print ( "-1" ) # Driver Code if __name__ = = "__main__" : # Given Bitwise AND, OR, and XOR n = 3 a = 4 b = 6 c = 6 # Function Call findArray(n, a, b, c) # This code is contributed by Chitranayal |
C #
// C# program for the above approach using System; class GFG{ // Function to find the array static void findArray( int n, int a, int b, int c) { int []arr = new int [n + 1]; // Loop through all bits in number for ( int bit = 30; bit >= 0; bit--) { // If bit is set in AND // then set it in every element // of the array int set = a & (1 << bit); if ( set != 0) { for ( int i = 0; i < n; i++) arr[i] |= set ; } // If bit is not set in AND else { // But set in b(OR) if ((b & (1 << bit)) != 0) { // Set bit position // in first element arr[0] |= (1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if ((c & (1 << bit)) == 0) { arr[1] |= (1 << bit); } } } } int aa = int .MaxValue, bb = 0, cc = 0; // Calculate AND, OR // and XOR of array for ( int i = 0; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // If not, then array // is not possible else Console.WriteLine( "-1" ); } // Driver code public static void Main(String[] args) { // Given Bitwise AND, OR, and XOR int n = 3, a = 4, b = 6, c = 6; // Function Call findArray(n, a, b, c); } } // This code is contributed by gauravrajput1 |
6 4 4
Сложность времени: O (31 * N)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.