Given an integer N, the task is to construct an array of N distinct elements (arr[i] ≤ N+1) such that the bitwise XOR of every prefix having an even length is either 0 or 1.
Examples:
Input: N = 5
Output = 2 3 4 5 6
Explanation: XOR from arr[1] to arr[2] = XOR(2, 3) = 1
XOR from arr[1] to arr[4] = XOR(2, 3, 4, 5) = 0Input: N = 2
Output: 2 3
Approach: The approach to the problem is based on the following observation
2*k XOR (2*k + 1) = 1 where k ∈ [1, ∞)
The above equation can be proved as shown below:
- 2k is an even number whose LSB is always zero. Adding 1 in this (resulting in 2k+1) will change only one bit of the number (LSB will get transformed from zero to one).
- Now, 2k and 2k+1 differ in only one bit at the 0th position. So, 2*k XOR 2*k+1 = 1.
So, if started from k = 1, and consecutive k‘s are considered the conditions will be satisfied and all the prefixes with even length will have XOR as 1 or 0(when prefix length is divisible by 4. because XOR of even number of 1 will be 0)
Follow the steps mentioned below to implement the above observation:
- Declare a vector to store the answer.
- Run a loop from i = 1 to n/2 and in each iteration:
- store two values in the vector:
- First Value = 2*i.
- Second Value = 2*i + 1.
- store two values in the vector:
- If N is odd, insert the last element (N + 1) in the vector because using the above method only an even number of elements can be inserted.
- Return the vector as this is the required array.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to construct the arrayvector<int> construct_arr(int n){ vector<int> ans; for (int i = 1; i <= n / 2; i++) { ans.push_back(2 * i); ans.push_back(2 * i + 1); } // If n is odd insert the last element if ((n % 2) != 0) { ans.push_back(n + 1); } return ans;}// Driver codeint main(){ int N = 5; // Function call vector<int> ans = construct_arr(N); // Print the resultant array for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // Java program for the above approach // Function to construct the array static ArrayList<Integer> construct_arr(int n) { ArrayList<Integer> ans = new ArrayList<Integer>(); for (int i = 1; i <= n / 2; i++) { ans.add(2*i); ans.add(2*i+1); } // If n is odd insert the last element if ((n % 2) != 0) { ans.add(n + 1); } return ans; } // Driver Code public static void main(String args[]) { int N = 5; // Function call ArrayList<Integer> ans = construct_arr(N); // Print the resultant array for (int i = 0; i < ans.size(); i++) System.out.print(ans.get(i) + " "); }}// This code is contributed by shinjanpatra. |
Python3
# python code to implement the approach# Function to construct the arraydef construct_arr(n): ans = [] for i in range(1, n//2+1): ans.append(2 * i) ans.append(2 * i + 1) # If n is odd insert the last element if ((n % 2) != 0): ans.append(n + 1) return ans# Driver codeif __name__ == "__main__": N = 5 # Function call ans = construct_arr(N) # Print the resultant array for i in range(0, len(ans)): print(ans[i], end=" ") # This code is contributed by rakeshsahni |
C#
// C# program for the above appraochhusing System;using System.Collections.Generic;class GFG { // Function to construct the array static List<int> construct_arr(int n) { List<int> ans = new List<int>(); for (int i = 1; i <= n / 2; i++) { ans.Add(2 * i); ans.Add(2 * i + 1); } // If n is odd insert the last element if ((n % 2) != 0) { ans.Add(n + 1); } return ans; } // Driver Code public static void Main(string[] args) { int N = 5; // Function call List<int> ans = construct_arr(N); // Print the resultant array for (int i = 0; i < ans.Count; i++) Console.Write(ans[i] + " "); }}// This code is contributed by phasing17 |
Javascript
<script> // JavaScript code for the above approach // Function to construct the array function construct_arr(n) { let ans = []; for (let i = 1; i <= Math.floor(n / 2); i++) { ans.push(2 * i); ans.push(2 * i + 1); } // If n is odd insert the last element if ((n % 2) != 0) { ans.push(n + 1); } return ans; } // Driver code let N = 5; // Function call let ans = construct_arr(N); // Print the resultant array for (let i = 0; i < ans.length; i++) document.write(ans[i] + " ") // This code is contributed by Potta Lokesh </script> |
Output
2 3 4 5 6
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
