Construct an array whose Prefix XOR array starting from X is an N-length increasing sequence
Given two integers N and X, the task is to generate an array of size N, such that the prefix xor array of X with the generated array will be permutations of 1st N natural numbers.
Examples:
Input: N = 4, X = 3
Output: [2, 3, 1, 7]
Explanation: Prefix XOR array for the array {2, 3, 1, 7} is as follows:
- X ? 2 = 1. Now, X = 1
- X ? 3 = 2. Now, X = 2
- X ? 1 = 3. Now, X = 3
- X ? 7 = 4. Now, X = 4
The array [1, 2, 3, 4] is a permutation of first 4 natural numbers.
Input: N = 7, X = 52
Output: [53, 3, 1, 7, 1, 3, 1]
Approach: This problem can be solved using the properties of XOR ( If x ? a = b, then x ? b = a). Suppose XOR of elements in the generated array with X till ith index is X, and (i + 1)th element of the generated array is B, then B can be calculated using the following steps :
X ? B = i + 1
According to problem statement, using the property of XOR (if x? a = b then, x? b = a)…
X ? i + 1 = B
Or
B = X ? i + 1, which is the required value of B.
Follow the steps below to solve the problem:
- Initialize a variable, say prev_xor as X.
- Iterate a loop using a variable, say i, from 1 to N and print prev_xor ? i.
- Update prev_xor as i.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the required array void GenerateArray( int N, int X) { int prev_xor = X; // Iterative from 1 to N for ( int i = 1; i <= N; i++) { // Print the i-th element cout << (i ^ prev_xor); if (i != N) { cout << " " ; } // Update prev_xor to i prev_xor = i; } } // Driver Code int main() { // Given Input int N = 4, X = 3; // Function Call cout << "The generated array is " ; GenerateArray(N, X); return 0; } |
Java
// Java program for the above approach class GFG { // Function to print the required array static void GenerateArray( int N, int X) { int prev_xor = X; // Iterative from 1 to N for ( int i = 1 ; i <= N; i++) { // Print the i-th element System.out.print(i ^ prev_xor); if (i != N) { System.out.print( " " ); } // Update prev_xor to i prev_xor = i; } } // Driver Code public static void main(String args[]) { // Given Input int N = 4 , X = 3 ; // Function Call System.out.print( "The generated array is " ); GenerateArray(N, X); } } // This code is contributed by splevel62. |
Python3
# Python 3 program for the above approach # Function to print the required array def GenerateArray(N, X): prev_xor = X # Iterative from 1 to N for i in range ( 1 ,N + 1 , 1 ): # Print the i-th element print (i ^ prev_xor,end = "") if (i ! = N): print ( " " ,end = "") # Update prev_xor to i prev_xor = i # Driver Code if __name__ = = '__main__' : # Given Input N = 4 X = 3 # Function Call print ( "The generated array is " ,end = "") GenerateArray(N, X) # This code is contributed by ipg2016107 |
C#
// C# program for above approach using System; class GFG { // Function to print the required array static void GenerateArray( int N, int X) { int prev_xor = X; // Iterative from 1 to N for ( int i = 1; i <= N; i++) { // Print the i-th element Console.Write(i ^ prev_xor); if (i != N) { Console.Write( " " ); } // Update prev_xor to i prev_xor = i; } } // Driver Code static void Main() { // Given Input int N = 4, X = 3; // Function Call Console.Write( "The generated array is " ); GenerateArray(N, X); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach; // Function to print the required array function GenerateArray(N, X) { let prev_xor = X; // Iterative from 1 to N for (let i = 1; i <= N; i++) { // Print the i-th element document.write((i ^ prev_xor)); if (i != N) { document.write( " " ); } // Update prev_xor to i prev_xor = i; } } // Driver Code // Given Input let N = 4, X = 3; // Function Call document.write( "The generated array is " ); GenerateArray(N, X); // This code is contributed by Potta Lokesh </script> |
The generated array is 2 3 1 7
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us