Given two positive integers N and K, the task is to construct N positive integers having Bitwise XOR of all these integers equal to K.
Examples:
Input: N = 4, K = 6
Output: 1 0 2 5
Explanation: Bitwise XOR the integers {1, 0, 2, 5} = 1 XOR 0 XOR 2 XOR 5 = 6(= K).Input: N = 1, K = 1
Output: 1
Approach: The idea to solve this problem is to include the first (N – 3) natural numbers and calculate their Bitwise XOR and select the remaining 3 integers based on the calculated XOR values. Follow the steps below to solve the problem:
- If N = 1: Print the integer K itself.
- If N = 2: Print K and 0 as the required output.
- Otherwise, consider the first (N – 3) natural numbers.
- Now, calculate Bitwise XOR of (N – 3) elements and store it in a variable, say val. The remaining three elements can be selected based on the following conditions:
- Case 1: If val is equal to K, perform the following steps:
- In this case, the Bitwise XOR of the remaining three elements needs to be equal to zero to make Bitwise XOR of all integers equal to K.
- Therefore, the remaining three elements must be P, Q, P XOR Q, thus making their Bitwise XOR equal to 0. But P XOR Q must be greater than N-2(i.e. P) so that all the numbers should remain distinct. ( In case, if you are wondering P XOR Q should also not be equal to Q, well this is not possible since the value of P will never be zero.
- Case (i): P XOR Q is already greater than P :
- The remaining three elements will be P, Q, P XOR Q.
- Case (ii): P XOR Q is not greater than P :
- Here, we will use the while loop with condition P XOR Q <= P with increment on Q by 1. After the termination of the loop, the remaining three elements will be P, Q, P XOR Q.
- Case 2: If val is not equal to K, perform the following steps:
- In this case, Bitwise XOR of the remaining three elements together with Bitwise XOR of the first (N – 3) elements needs to be equal to K.
- By considering the last 3 elements to be equal to 0, P, P XOR K XOR val, Bitwise XOR of these three elements is equal to K XOR val. Again, P XOR K XOR val must be greater than N-2 for all the N numbers to be distinct.
- Case (i): P XOR K XOR val is already greater than N-2 :
- The remaining three elements will be 0, P, P XOR K XOR val.
- Case (ii): P XOR K XOR val is not greater than N-2:
- Here, we will use the while loop with condition P XOR K XOR val <= N-2 with increment on P by 1. After the termination of loop, the remaining three elements will be 0, P, P XOR K XOR val.
- Case 1: If val is equal to K, perform the following steps:
- Choosing P and Q: For both cases, the value of P and Q requires to be distinct from the first (N – 3) elements. Therefore, consider P and Q to be (N – 2) and (N – 1).
- In case you are wondering that while loops may be stuck for too long, is not true. You will generally get the number in the range of 100 iterations. So on average, the time complexity of both the while loops mentioned in cases 1 and 2 is almost constant.
Below is the implementation of the above solution:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find N integers// having Bitwise XOR equal to Kvoid findArray(int N, int K){ // Base Cases if (N == 1) { cout << " " << K; return; } if (N == 2) { cout << 0 << " " << K; return; } // Assign values to P and Q int P = N - 2; int Q = N - 1; // Stores Bitwise XOR of the // first (N - 3) elements int VAL = 0; // Print the first N - 3 elements for(int i = 1; i <= (N - 3); i++) { cout << " " << i; // Calculate Bitwise XOR of // first (N - 3) elements VAL ^= i; } if (VAL == K) { // checking whether P ^ Q is greater than P or not. while( (P ^ Q) <= P) { Q++; } cout << " " << P << " " << Q << " " << (P ^ Q); } else { // checking whether P ^ K ^ VAL is greater than N-2 or not. while( (P ^ K ^ VAL) <= N-3) { P++; } cout << " " << 0 << " " << P << " " << (P ^ K ^ VAL); }}// Driver Codeint main(){ int N = 4, X = 6; // Function Call findArray(N, X); return 0;}// This code is contributed by shivanisinghss2110 |
C
// C program for the above approach#include <stdio.h>// Function to find N integers// having Bitwise XOR equal to Kvoid findArray(int N, int K){ // Base Cases if (N == 1) { printf("%d", K); return; } if (N == 2) { printf("%d %d", 0, K); return; } // Assign values to P and Q int P = N - 2; int Q = N - 1; // Stores Bitwise XOR of the // first (N - 3) elements int VAL = 0; // Print the first N - 3 elements for (int i = 1; i <= (N - 3); i++) { printf("%d ", i); // Calculate Bitwise XOR of // first (N - 3) elements VAL ^= i; } if (VAL == K) { // checking whether P ^ Q is greater than P or not. while( (P ^ Q) <= P) { Q++; } printf("%d %d %d", P, Q, P ^ Q); } else { // checking whether P ^ K ^ VAL is greater than N-2 or not. while( (P ^ K ^ VAL) <= N-2) { P++; } printf("%d %d %d", 0, P, P ^ K ^ VAL); }}// Driver Codeint main(){ int N = 4, X = 6; // Function Call findArray(N, X); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG{// Function to find N integers// having Bitwise XOR equal to Kstatic void findArray(int N, int K){ // Base Cases if (N == 1) { System.out.print(K + " "); return; } if (N == 2) { System.out.print(0 + " " + K); return; } // Assign values to P and Q int P = N - 2; int Q = N - 1; // Stores Bitwise XOR of the // first (N - 3) elements int VAL = 0; // Print the first N - 3 elements for(int i = 1; i <= (N - 3); i++) { System.out.print(i + " "); // Calculate Bitwise XOR of // first (N - 3) elements VAL ^= i; } if (VAL == K) { // checking whether P ^ Q is greater than P or not. while( (P ^ Q) <= P) { Q++; } System.out.print(P + " " + Q + " " + (P ^ Q)); } else { // checking whether P ^ K ^ VAL is greater than N-2 or not. while( (P ^ K ^ VAL) <= N-2) { P++; } System.out.print(0 + " " + P + " " + (P ^ K ^ VAL)); }} // Driver Codepublic static void main(String[] args){ int N = 4, X = 6; // Function Call findArray(N, X);}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach# Function to find N integers# having Bitwise XOR equal to Kdef findArray(N, K): # Base Cases if (N == 1): print(K, end=" ") return if (N == 2): print("0", end=" ") print(K, end=" ") return # Assign values to P and Q P = N - 2 Q = N - 1 # Stores Bitwise XOR of the # first (N - 3) elements VAL = 0 # Print the first N - 3 elements for i in range(1, N - 2): print(i, end=" ") # Calculate Bitwise XOR of # first (N - 3) elements VAL ^= i if (VAL == K): # checking whether P ^ Q is greater than P or not. while ((P ^ Q) <= P): Q = Q + 1 print(P, end=" ") print(Q, end=" ") print(P ^ Q, end=" ") else: # checking whether P ^ K ^ VAL is greater than N-2 or not. while ((P ^ K ^ VAL) <= N - 2): P = P + 1 print("0", end=" ") print(P, end=" ") print(P ^ K ^ VAL, end=" ")# Driver CodeN = 4X = 6# Function CallfindArray(N, X)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find N integers// having Bitwise XOR equal to Kstatic void findArray(int N, int K){ // Base Cases if (N == 1) { Console.Write(K + " "); return; } if (N == 2) { Console.Write(0 + " " + K); return; } // Assign values to P and Q int P = N - 2; int Q = N - 1; // Stores Bitwise XOR of the // first (N - 3) elements int VAL = 0; // Print the first N - 3 elements for (int i = 1; i <= (N - 3); i++) { Console.Write(i + " "); // Calculate Bitwise XOR of // first (N - 3) elements VAL ^= i; } if (VAL == K) { // checking whether P ^ Q is greater than P or not. while( (P ^ Q) <= P) { Q++; } Console.Write(P + " " + Q + " " + (P ^ Q)); } else { // checking whether P ^ K ^ VAL is greater than N-2 or not. while( (P ^ K ^ VAL) <= N-2) { P++; } Console.Write(0 + " " + P + " " + (P ^ K ^ VAL)); }} // Driver Codepublic static void Main(){ int N = 4, X = 6; // Function Call findArray(N, X);}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to find N integers// having Bitwise XOR equal to Kfunction findArray(N, K){ // Base Cases if (N == 1) { document.write(K + " "); return; } if (N == 2) { document.write(0 + " " + K); return; } // Assign values to P and Q let P = N - 2; let Q = N - 1; // Stores Bitwise XOR of the // first (N - 3) elements let VAL = 0; // Print the first N - 3 elements for(let i = 1; i <= (N - 3); i++) { document.write(i + " "); // Calculate Bitwise XOR of // first (N - 3) elements VAL ^= i; } if (VAL == K) { // checking whether P ^ Q is greater than P or not. while( (P ^ Q) <= P) { Q++; } document.write(P + " " + Q + " " + (P ^ Q)); } else { // checking whether P ^ K ^ VAL is greater than N-2 or not. while( (P ^ K ^ VAL) <= N-2) { P++; } document.write(0 + " " + P + " " + (P ^ K ^ VAL)); }}// Driver Code let N = 4, X = 6; // Function Call findArray(N, X); </script> |
Output:
1 0 2 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
