Создайте массив, используя заданные побитовые операции AND, OR и XOR.

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

Даны побитовые операции И , ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ для 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 
 

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

Подход:

  1. Для побитового И , если i- й бит установлен в a , то в массиве для каждого элемента должен быть установлен i- й бит, потому что если даже один элемент i- й бит равен 0, то побитовое И массива приведет к тому, что i- й бит будет равен 0 .
  2. Во-вторых, если i- й бит не установлен в a, то значения OR и XOR необходимо обрабатывать одновременно. Если i- й бит установлен в b , то хотя бы в одном элементе должен быть установлен i- й бит. Итак, установите i- й бит в единственный первый элемент массива.
  3. Теперь, если i- й бит был установлен в b, то i- й бит должен быть проверен в c . Если этот бит установлен в c, то проблем нет, поскольку i- й бит первого элемента уже установлен, поэтому 1 ^ 0 = 1. Если этот бит не установлен в c, установите i- й бит второго элемента. Теперь в b не будет никакого эффекта, а для c 1 ^ 1 будет 0 .
  4. Затем просто вычислите побитовое И, ИЛИ и 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.

Олимпиады по программированию Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022