Dados cuatro números L, R, K y X , la tarea es encontrar K números decimales distintos en el rango [L, R] de modo que su XOR bit a bit sea X .
Nota: Si hay más de una posibilidad, imprima cualquiera de ellas.
Ejemplos:
Entrada: L = 1 , R = 13, K = 5, X = 11
Salida: 2 3 8 9 11
Explicación: 2 ⊕ 3 ⊕ 8 ⊕ 9 ⊕ 11 = 11Entrada: L = 1, R = 10, K = 3, X = 5
Salida: 1 2 6
Explicación: 1 ⊕ 2 ⊕ 6 = 5.
Hay otra posibilidad, es decir, {2, 3, 4}.
Enfoque: El problema se puede resolver con base en la idea de la combinatoria de la siguiente manera:
Tenemos que generar K elementos a partir de (R – L). Así que hay un total de RL C K opciones posibles. Estas opciones se pueden generar con la ayuda de retroceder .
Siga los pasos mencionados a continuación para implementar la idea:
- Llame a la función de retroceso desde L .
- Cada elemento tiene dos opciones: elegirlo o no.
- Si se consideran los K elementos totales, no podemos elegir otro elemento.
- De lo contrario, elija el elemento y considérelo como parte de la respuesta.
- Si esa elección no satisface la condición, elimínela y continúe con los demás elementos.
- Si la respuesta se encuentra en cualquier momento, no es necesario recorrer las otras opciones y devolver el mismo grupo de elementos que la respuesta.
- Si el elemento actual no se considera como parte de la respuesta, no lo incluya y continúe con el siguiente entero.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// To denote if the numbers are found
bool flag;
// Function to implement the backtracking
// to get K numbers whose XOR is X
void helper(int i, int r, int cnt, int tmp,
int x, vector<int>& v)
{
if (i > r)
return;
// If K elements are found
// satisfying the condition
if (i == r and tmp == x and cnt == 0)
flag = true;
// Current element is selected
if (cnt > 0) {
v.push_back(i);
helper(i + 1, r, cnt - 1, tmp ^ i, x, v);
if (flag)
return;
v.pop_back();
}
// Current element is not selected
helper(i + 1, r, cnt, tmp, x, v);
}
// Function to invoke the helper function
vector<int> solve(int l, int r, int k, int x)
{
vector<int> res;
flag = false;
helper(l, r, k, 0, x, res);
return res;
}
// Driver code
int main()
{
int L = 1, R = 10, K = 3, X = 5;
// Function call
vector<int> ans = solve(L, R, K, X);
if (ans.size() == 0)
cout << "Not Possible";
else {
for (int x : ans)
cout << x << " ";
}
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// To denote if the numbers are found
public static boolean flag = false;
// Function to implement the backtracking to get K
// numbers whose XOR is X
public static void helper(int i, int r, int cnt,
int tmp, int x,
List<Integer> v)
{
if (i > r) {
return;
}
// If K elements are found satisfying the condition
if (i == r && tmp == x && cnt == 0) {
flag = true;
}
// Current element is selected
if (cnt > 0) {
v.add(i);
helper(i + 1, r, cnt - 1, tmp ^ i, x, v);
if (flag == true) {
return;
}
v.remove(v.size() - 1);
}
// Current element is not selected
helper(i + 1, r, cnt, tmp, x, v);
}
// Function to invoke the helper function
public static List<Integer> solve(int l, int r, int k,
int x)
{
List<Integer> res = new ArrayList<>();
helper(l, r, k, 0, x, res);
return res;
}
public static void main(String[] args)
{
int L = 1, R = 10, K = 3, X = 5;
// Function call
List<Integer> ans = solve(L, R, K, X);
if (ans.size() == 0) {
System.out.print("Not Possible");
}
else {
for (int i : ans) {
System.out.print(i + " ");
}
}
}
}
// This code is contributed by lokesh (lokeshmvs21).
Python3
# python3 code to implement the approach
# To denote if the numbers are found
flag = False
# Function to implement the backtracking
# to get K numbers whose XOR is X
def helper(i, r, cnt, tmp, x, v):
global flag
if (i > r):
return
# If K elements are found
# satisfying the condition
if (i == r and tmp == x and cnt == 0):
flag = True
# Current element is selected
if (cnt > 0):
v.append(i)
helper(i + 1, r, cnt - 1, tmp ^ i, x, v)
if (flag):
return
v.pop()
# Current element is not selected
helper(i + 1, r, cnt, tmp, x, v)
# Function to invoke the helper function
def solve(l, r, k, x):
global flag
res = []
flag = False
helper(l, r, k, 0, x, res)
return res
# Driver code
if __name__ == "__main__":
L = 1
R = 10
K = 3
X = 5
# Function call
ans = solve(L, R, K, X)
if (len(ans) == 0):
print("Not Possible")
else:
for x in ans:
print(x, end=" ")
# This code is contributed by rakeshsahni
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// To denote if the numbers are found
public static bool flag = false;
// Function to implement the backtracking to get K
// numbers whose XOR is X
public static void helper(int i, int r, int cnt,
int tmp, int x,
List<int> v)
{
if (i > r) {
return;
}
// If K elements are found satisfying the condition
if (i == r && tmp == x && cnt == 0) {
flag = true;
}
// Current element is selected
if (cnt > 0) {
v.Add(i);
helper(i + 1, r, cnt - 1, tmp ^ i, x, v);
if (flag == true) {
return;
}
v.RemoveAt(v.Count - 1);
}
// Current element is not selected
helper(i + 1, r, cnt, tmp, x, v);
}
// Function to invoke the helper function
public static List<int> solve(int l, int r, int k,
int x)
{
List<int> res = new List<int>();
helper(l, r, k, 0, x, res);
return res;
}
public static void Main(string[] args)
{
int L = 1, R = 10, K = 3, X = 5;
// Function call
List<int> ans = solve(L, R, K, X);
if (ans.Count == 0) {
Console.WriteLine("Not Possible");
}
else {
foreach (int i in ans) {
Console.Write(i + " ");
}
}
}
}
// This code is contributed by phasing17
Javascript
<script>
// javascript code to implement the approach
// To denote if the numbers are found
let flag = false;
var res = new Array();
// Function to implement the backtracking to get K
// numbers whose XOR is X
function helper(i , r , cnt, tmp , x, v)
{
if (i > r) {
return;
}
// If K elements are found satisfying the condition
if (i == r && tmp == x && cnt == 0) {
flag = true;
}
// Current element is selected
if (cnt > 0) {
v.push(i);
helper(i + 1, r, cnt - 1, tmp ^ i, x, v);
if (flag == true) {
return;
}
v.pop(v.length-1);
}
// Current element is not selected
helper(i + 1, r, cnt, tmp, x, v);
}
// Function to invoke the helper function
function solve(l , r , k,x)
{
helper(l, r, k, 0, x, res);
}
var L = 1, R = 10, K = 3, X = 5;
// Function call
solve(L, R, K, X);
if (res.length == 0) {
document.write("Not Possible");
}
else {
for (var i =0; i<res.length; i++)
document.write(res[i] + " ");
}
// This code contributed by shikhasingrajput
</script>
Producción
1 2 6
Complejidad temporal: O(N K )
Espacio auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por kingrishabdugar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA