Horje
Find K numbers in a given range [L, R] such that their bitwise XOR is X

Given four numbers L, R, K, and X, the task is to find K distinct decimal numbers in the range [L, R] such that their bitwise XOR is X.

Note: If there are more than one possibilities, print any one of them.

Examples:

Input: L = 1  , R = 13, K = 5, X = 11
Output: 2 3 8 9 11
Explanation: 2 ⊕ 3 ⊕ 8 ⊕ 9 ⊕ 11 = 11

Input: L = 1, R = 10, K = 3, X = 5
Output: 1 2 6
Explanation: 1 ⊕ 2 ⊕ 6 = 5. 
There is one other possibility i.e., {2, 3, 4}.

 

Approach: The problem can be solved based on the idea of combinatorics as follows:

We have to generate K elements from (R – L). So there are total R-LCK possible choices. These choices can be generated with the help of backtracking.

Follow the steps mentioned below to implement the idea:

  • Call the backtracking function from L.
  • Each element has two choices – either pick it or not.
    • If total K elements are considered, we cannot pick another element.
    • Otherwise, pick the element and consider that as a part of the answer.
      • If that choice does, not satisfy the condition, remove that and continue the same with the other elements.
      • If the answer is found at any moment, no need to traverse for the other options and return the same group of elements as the answer.
    • If the current element is not considered as a part of the answer, don’t include it and carry on the same from the next integer.

Below is the implementation of the above approach.

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>

Output

1 2 6

Time Complexity: O(NK)
Auxiliary Space: O(K)


 


Reffered: https://www.geeksforgeeks.org

Backtracking

Related
Print ways to obtain given sum by repeated throws of a dice Print ways to obtain given sum by repeated throws of a dice
Check if it’s possible to completely fill every container with same ball Check if it’s possible to completely fill every container with same ball
Least count of words required to construct a target String Least count of words required to construct a target String
Count of permutations of an Array having each element as a multiple or a factor of its index Count of permutations of an Array having each element as a multiple or a factor of its index
Generate all possible permutations of a Number divisible by N Generate all possible permutations of a Number divisible by N

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje