Dados dos enteros N y K , la tarea es encontrar N enteros distintos cuyo OR bit a bit sea igual a K . Si no existe ninguna respuesta posible, imprima -1 .
Ejemplos:
Entrada: N = 3, K = 5
Salida: 5 0 1
5 O 0 O 1 = 5
Entrada: N = 10, K = 5
Salida: -1
No es posible encontrar ninguna solución.
Acercarse:
- Sabemos que si el OR bit a bit de una secuencia de números es K , entonces todas las posiciones de bits que son 0 en K también deben ser cero en todos los números.
- Entonces, solo tenemos esas posiciones para cambiar donde el bit es 1 en K . Digamos que el recuento es Bit_K .
- Ahora, podemos formar pow(2, Bit_K) números distintos con Bit_K bits. Entonces, si configuramos un número para que sea K en sí mismo, entonces se pueden construir N – 1 números restantes configurando 0 todos los bits en cada número que son 0 en K y para otras posiciones de bits cualquier permutación de Bit_K bits que no sea el número K.
- Si pow(2, Bit_K) < N entonces no podemos encontrar ninguna respuesta posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX 32
ll pow2[MAX];
bool visited[MAX];
vector<int> ans;
// Function to pre-calculate
// all the powers of 2 upto MAX
void power_2()
{
ll ans = 1;
for (int i = 0; i < MAX; i++) {
pow2[i] = ans;
ans *= 2;
}
}
// Function to return the
// count of set bits in x
int countSetBits(ll x)
{
// To store the count
// of set bits
int setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Function to add num to the answer
// by setting all bit positions as 0
// which are also 0 in K
void add(ll num)
{
int point = 0;
ll value = 0;
for (ll i = 0; i < MAX; i++) {
// Bit i is 0 in K
if (visited[i])
continue;
else {
if (num & 1) {
value += (1 << i);
}
num /= 2;
}
}
ans.push_back(value);
}
// Function to find and print N distinct
// numbers whose bitwise OR is K
void solve(ll n, ll k)
{
// Choosing K itself as one number
ans.push_back(k);
// Find the count of set bits in K
int countk = countSetBits(k);
// Impossible to get N
// distinct integers
if (pow2[countk] < n) {
cout << -1;
return;
}
int count = 0;
for (ll i = 0; i < pow2[countk] - 1; i++) {
// Add i to the answer after
// setting all the bits as 0
// which are 0 in K
add(i);
count++;
// If N distinct numbers are generated
if (count == n)
break;
}
// Print the generated numbers
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
}
// Driver code
int main()
{
ll n = 3, k = 5;
// Pre-calculate all
// the powers of 2
power_2();
solve(n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static final int MAX = 32;
static long []pow2 = new long[MAX];
static boolean []visited = new boolean[MAX];
static Vector<Long> ans = new Vector<>();
// Function to pre-calculate
// all the powers of 2 upto MAX
static void power_2()
{
long ans = 1;
for (int i = 0; i < MAX; i++)
{
pow2[i] = ans;
ans *= 2;
}
}
// Function to return the
// count of set bits in x
static int countSetBits(long x)
{
// To store the count
// of set bits
int setBits = 0;
while (x != 0)
{
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Function to add num to the answer
// by setting all bit positions as 0
// which are also 0 in K
static void add(long num)
{
int point = 0;
long value = 0;
for (int i = 0; i < MAX; i++)
{
// Bit i is 0 in K
if (visited[i])
continue;
else
{
if (num %2== 1)
{
value += (1 << i);
}
num /= 2;
}
}
ans.add(value);
}
// Function to find and print N distinct
// numbers whose bitwise OR is K
static void solve(long n, long k)
{
// Choosing K itself as one number
ans.add(k);
// Find the count of set bits in K
int countk = countSetBits(k);
// Impossible to get N
// distinct integers
if (pow2[countk] < n)
{
System.out.print(-1);
return;
}
int count = 0;
for (long i = 0; i < pow2[countk] - 1; i++)
{
// Add i to the answer after
// setting all the bits as 0
// which are 0 in K
add(i);
count++;
// If N distinct numbers are generated
if (count == n)
break;
}
// Print the generated numbers
for (int i = 0; i < n; i++)
{
System.out.print(ans.get(i)+" ");
}
}
// Driver code
public static void main(String[] args)
{
long n = 3, k = 5;
// Pre-calculate all
// the powers of 2
power_2();
solve(n, k);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach MAX = 32 pow2 = [0 for i in range(MAX)] visited = [False for i in range(MAX)] ans = [] # Function to pre-calculate # all the powers of 2 upto MAX def power_2(): an = 1 for i in range(MAX): pow2[i] = an an *= 2 # Function to return the # count of set bits in x def countSetBits(x): # To store the count # of set bits setBits = 0 while (x != 0): x = x & (x - 1) setBits += 1 return setBits # Function to add num to the answer # by setting all bit positions as 0 # which are also 0 in K def add(num): point = 0 value = 0 for i in range(MAX): # Bit i is 0 in K if (visited[i]): continue else: if (num & 1): value += (1 << i) num = num//2 ans.append(value) # Function to find and print N distinct # numbers whose bitwise OR is K def solve(n, k): # Choosing K itself as one number ans.append(k) # Find the count of set bits in K countk = countSetBits(k) # Impossible to get N # distinct integers if (pow2[countk] < n): print(-1) return count = 0 for i in range(pow2[countk] - 1): # Add i to the answer after # setting all the bits as 0 # which are 0 in K add(i) count += 1 # If N distinct numbers are generated if (count == n): break # Print the generated numbers for i in range(n): print(ans[i],end = " ") # Driver code if __name__ == '__main__': n = 3 k = 5 # Pre-calculate all # the powers of 2 power_2() solve(n, k) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 32;
static long [] pow2 = new long[MAX];
static bool [] visited = new bool[MAX];
static List<long> ans = new List<long>();
// Function to pre-calculate
// all the powers of 2 upto MAX
static void power_2()
{
long ans = 1;
for (int i = 0; i < MAX; i++)
{
pow2[i] = ans;
ans *= 2;
}
}
// Function to return the
// count of set bits in x
static int countSetBits(long x)
{
// To store the count
// of set bits
int setBits = 0;
while (x != 0)
{
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Function to add num to the answer
// by setting all bit positions as 0
// which are also 0 in K
static void add(long num)
{
long value = 0;
for (int i = 0; i < MAX; i++)
{
// Bit i is 0 in K
if (visited[i])
continue;
else
{
if (num %2== 1)
{
value += (1 << i);
}
num /= 2;
}
}
ans.Add(value);
}
// Function to find and print N distinct
// numbers whose bitwise OR is K
static void solve(long n, long k)
{
// Choosing K itself as one number
ans.Add(k);
// Find the count of set bits in K
int countk = countSetBits(k);
// Impossible to get N
// distinct integers
if (pow2[countk] < n)
{
Console.WriteLine(-1);
return;
}
int count = 0;
for (long i = 0; i < pow2[countk] - 1; i++)
{
// Add i to the answer after
// setting all the bits as 0
// which are 0 in K
add(i);
count++;
// If N distinct numbers are generated
if (count == n)
break;
}
// Print the generated numbers
for (int i = 0; i < n; i++)
{
Console.Write(ans[i]+ " ");
}
}
// Driver code
public static void Main()
{
long n = 3, k = 5;
// Pre-calculate all
// the powers of 2
power_2();
solve(n, k);
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript implementation of the approach
const MAX = 32;
let pow2 = new Array(MAX);
let visited = new Array(MAX);
let ans = [];
// Function to pre-calculate
// all the powers of 2 upto MAX
function power_2()
{
let ans = 1;
for (let i = 0; i < MAX; i++) {
pow2[i] = ans;
ans *= 2;
}
}
// Function to return the
// count of set bits in x
function countSetBits(x)
{
// To store the count
// of set bits
let setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Function to add num to the answer
// by setting all bit positions as 0
// which are also 0 in K
function add(num)
{
let point = 0;
let value = 0;
for (let i = 0; i < MAX; i++) {
// Bit i is 0 in K
if (visited[i])
continue;
else {
if (num & 1) {
value += (1 << i);
}
num = parseInt(num / 2);
}
}
ans.push(value);
}
// Function to find and print N distinct
// numbers whose bitwise OR is K
function solve(n, k)
{
// Choosing K itself as one number
ans.push(k);
// Find the count of set bits in K
let countk = countSetBits(k);
// Impossible to get N
// distinct integers
if (pow2[countk] < n) {
document.write(-1);
return;
}
let count = 0;
for (let i = 0; i < pow2[countk] - 1; i++) {
// Add i to the answer after
// setting all the bits as 0
// which are 0 in K
add(i);
count++;
// If N distinct numbers are generated
if (count == n)
break;
}
// Print the generated numbers
for (let i = 0; i < n; i++) {
document.write(ans[i] + " ");
}
}
// Driver code
let n = 3, k = 5;
// Pre-calculate all
// the powers of 2
power_2();
solve(n, k);
</script>
Producción:
5 0 1
Complejidad de tiempo: O (MAX)
Espacio Auxiliar: O(MAX)