Создайте наименьший возможный массив с заданной суммой и XOR

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

Даны два положительных целых числа S и X, которые представляют сумму и побитовое исключающее ИЛИ всех элементов массива arr [] . Задача - найти элементы массива arr [] . Если такой массив не может быть сгенерирован, выведите -1.
Примеры:

Input: Sum = 4, Xor = 2 
Output: {3, 1} 
Explanation: 
Sum of 1 and 3 is 4. 
Bitwise XOR of 1 and 3 is 2.
Input: Sum = 5, Xor = 8 
Output: -1 
Explanation: 
There is no such array exists. 
 

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

Подход: можно доказать, что максимальная длина массива не превосходит 3. Рассмотрим следующие случаи:

  • Случай 1. Если заданная сумма и побитовое исключающее ИЛИ равны и не равны нулю, то этот элемент будет единственным элементом требуемого массива.
  • Случай 2: для неравной суммы и побитового XOR самая короткая длина массива может быть 2 или 3.
    Если заданные побитовое исключающее ИЛИ и сумма равны a и b соответственно, то самый короткий массив может быть {a, (b - a) / 2, (ba) / 2}, используя следующие два свойства XOR:
    • а Xor 0 = а
    • а X или а = 0
  • Случай 3: когда длина массива может быть 2.
    Массив, который мы взяли в предыдущем случае, можно сократить до двух элементов, если это возможно.

Здесь может помочь одна важная формула:

p + q = (p ^ q) + 2*(p & q) 
 

Подставляя значения sum и xor в приведенную выше формулу, мы получаем очень полезное соотношение.

b = a + 2*(p & q) 
(p & q) = (b-a)/2 
From previous case,  
x = (b-a)/2 = (p & q) 

Итак, теперь давайте посмотрим на некоторую связь между a (заданным xor) и x ((ba) / 2).

 pqa = (p ^ q) x = (p & q) a & x
0 0 0 0 0
0 1 1 0 0
1 0 1 0 0
1 1 0 1 0
  • Примечание: p и q представляют все соответствующие 32 бита двух чисел в массиве.

Важно отметить, что если a & x становится равным нулю, тогда a + x = a ^ x, что означает, что массив будет уменьшен до {a + x, x}, потому что a + x = a ^ x . Из приведенной выше формулы, которая все еще может привести к общему XOR как a, а сумма все равно будет b, поскольку x равно (ba) / 2.

  • Случай 4: Единственный оставшийся случай - проверить, существует ли массив или нет. В этом случае нужно проверить только два условия:
    1. Если побитовое исключающее ИЛИ больше суммы.
    2. Если sum и xor имеют разную четность, т. Е. Одно четное, а другое нечетное.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find array
void findArray( int sum, int xorr)
{
// array not possible
if (xorr > sum
|| sum % 2 != xorr % 2) {
cout << "No Array Possible " ;
return ;
}
// Array possible with exactly 1
// or no element
if (sum == xorr) {
if (sum == 0)
cout << "Array is empty"
<< " with size 0 " ;
else
cout << "Array size is "
<< 1
<< " Array is "
<< sum << " " ;
return ;
}
int mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr & mid == 1) {
cout << "Array size is "
<< 3 << " " ;
cout << "Array is "
<< xorr << " "
<< mid << " "
<< mid << " " ;
}
else {
cout << "Array size is "
<< 2 << " " ;
cout << "Array is "
<< (xorr + mid)
<< " "
<< mid << " " ;
}
}
// Driver Code
int main()
{
// Given sum and value
// of Bitwise XOR
int sum = 4, xorr = 2;
// Function Call
findArray(sum, xorr);
cout << " " ;
return 0;
}

Джава

// Java program implementation
// of the approach
import java.util.*;
import java.io.*;
class GFG{
// Function to find array
static void findArray( int sum, int xorr)
{
// Array not possible
if (xorr > sum || sum % 2 != xorr % 2 )
{
System.out.println( "No Array Possible" );
return ;
}
// Array possible with exactly 1
// or no element
if (sum == xorr)
{
if (sum == 0 )
System.out.println( "Array is empty " +
"with size 0" );
else
System.out.println( "Array size is " + 1 );
System.out.println( "Array is " + sum);
return ;
}
int mid = (sum - xorr) / 2 ;
// Checking array with two
// elements possible or not.
if (xorr == 1 && mid == 1 )
{
System.out.println( "Array size is " + 3 );
System.out.println( "Array is " + xorr +
" " + mid + " " + mid);
}
else
{
System.out.println( "Array size is " + 2 );
System.out.println( "Array is " + (xorr + mid) +
" " + mid);
}
}
// Driver code
public static void main(String[] args)
{
// Given sum and value
// of Bitwise XOR
int sum = 4 , xorr = 2 ;
// Function call
findArray(sum, xorr);
}
}
// This code is contributed by sanjoy_62

Python3

# Python3 program for the above approach
# Function to find array
def findArray(_sum, xorr):
# Array not possible
if (xorr > _sum or
_sum % 2 ! = xorr % 2 ):
print ( "No Array Possible" )
return
# Array possible with exactly 1
# or no element
if (_sum = = xorr):
if (_sum = = 0 ):
print ( "Array is empty" ,
" with size 0" )
else :
print ( "Array size is" , 1 )
print ( "Array is" , _sum)
return
mid = (_sum - xorr) / / 2
# Checking array with two
# elements possible or not.
if (xorr & mid = = 1 ):
print ( "Array size is" , 3 )
print ( "Array is" , xorr, mid, mid)
else :
print ( "Array size is" , 2 )
print ( "Array is" ,(xorr + mid), mid)
# Driver Code
# Given sum and value
# of Bitwise XOR
_sum = 4
xorr = 2
# Function Call
findArray(_sum, xorr)
# This code is contributed by divyamohan123

C #

// C# program implementation
// of the approach
using System;
class GFG{
// Function to find array
static void findArray( int sum, int xorr)
{
// Array not possible
if (xorr > sum || sum % 2 != xorr % 2)
{
Console.WriteLine( "No Array Possible" );
return ;
}
// Array possible with exactly 1
// or no element
if (sum == xorr)
{
if (sum == 0)
Console.WriteLine( "Array is empty " +
"with size 0" );
else
Console.WriteLine( "Array size is " + 1);
Console.WriteLine( "Array is " + sum);
return ;
}
int mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr == 1 && mid == 1)
{
Console.WriteLine( "Array size is " + 3);
Console.WriteLine( "Array is " + xorr +
" " + mid + " " + mid);
}
else
{
Console.WriteLine( "Array size is " + 2);
Console.WriteLine( "Array is " + (xorr + mid) +
" " + mid);
}
}
// Driver code
public static void Main()
{
// Given sum and value
// of Bitwise XOR
int sum = 4, xorr = 2;
// Function call
findArray(sum, xorr);
}
}
// This code is contributed by sanjoy_62

Javascript

<script>
// Javascript program implementation
// of the approach
// Function to find array
function findArray(sum, xorr)
{
// Array not possible
if (xorr > sum || sum % 2 != xorr % 2)
{
System.out.println( "No Array Possible" );
return ;
}
// Array possible with exactly 1
// or no element
if (sum == xorr)
{
if (sum == 0)
document.write( "Array is empty " +
"with size 0" );
else
document.write( "Array size is " + 1);
document.write( " Array is " + sum);
return ;
}
var mid = (sum - xorr) / 2;
// Checking array with two
// elements possible or not.
if (xorr == 1 && mid == 1)
{
document.write( "Array size is " + 3);
document.write( "Array is " + xorr +
" " + mid + " " + mid);
}
else
{
document.write( "Array size is " + 2);
document.write( "<br>" )
document.write( "Array is " + (xorr + mid) +
" " + mid);
}
}
// Driver code
// Given sum and value
// of Bitwise XOR
var sum = 4, xorr = 2;
// Function call
findArray(sum, xorr);
// This code is contributed by Khushboogoyal499
</script>
Выход:
 Размер массива 2
Массив равен 3 1

Сложность времени: O (1)
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции 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