Given a positive integer N, the task is to print all the distinct even and odd values of prefix Bitwise XORs of first N natural numbers.
Examples:
Input: N = 6
Output:
Even: 0 4
Odd: 1 3 7
Explanation:
The prefix Bitwise XOR of the first 6 natural number si {1, 3, 0, 4, 1, 7}.
Even prefix Bitwise XORs are 0, 4.
Odd prefix Bitwise XORs are 1, 3, 7.Input: N = 9
Output:
Even: 0 4 8
Odd: 1 3 7
Approach: The given problem can be solved based on the below observations:
- If the value of N modulo 4 is 0, then the value of Bitwise XOR of the first N natural numbers is N.
- If the value of N modulo 4 is 1, then the value of Bitwise XOR of the first N natural numbers is 1.
- If the value of N modulo 4 is 2, then the value of Bitwise XOR of the first N natural numbers is (N + 1).
- If the value of N modulo 4 is 3, then the value of Bitwise XOR of the first N natural numbers is 0.
Therefore, from the above principle, it can be said that Bitwise XOR as even numbers will always come as 0 or multiples of 4, and Bitwise XOR as odd numbers will always come as 1 or 1 less than multiples of 4.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Print all distinct even & odd // prefix Bitwise XORs from 1 to N void evenOddBitwiseXOR( int N) { cout << "Even: " << 0 << " " ; // Print the even number for ( int i = 4; i <= N; i = i + 4) { cout << i << " " ; } cout << "\n" ; cout << "Odd: " << 1 << " " ; // Print the odd number for ( int i = 4; i <= N; i = i + 4) { cout << i - 1 << " " ; } if (N % 4 == 2) cout << N + 1; else if (N % 4 == 3) cout << N; } // Driver Code int main() { int N = 6; evenOddBitwiseXOR(N); return 0; } |
Java
// Java approach for the above approach class GFG{ // Print all distinct even & odd // prefix Bitwise XORs from 1 to N static void evenOddBitwiseXOR( int N) { System.out.print( "Even: " + 0 + " " ); // Print the even number for ( int i = 4 ; i <= N; i = i + 4 ) { System.out.print(i + " " ); } System.out.print( "\n" ); System.out.print( "Odd: " + 1 + " " ); // Print the odd number for ( int i = 4 ; i <= N; i = i + 4 ) { System.out.print(i - 1 + " " ); } if (N % 4 == 2 ) System.out.print(N + 1 ); else if (N % 4 == 3 ) System.out.print(N); } // Driver Code public static void main(String[] args) { int N = 6 ; evenOddBitwiseXOR(N); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Print all distinct even & odd # prefix Bitwise XORs from 1 to N def evenOddBitwiseXOR(N): print ( "Even: " , 0 , end = " " ) # Print the even number for i in range ( 4 , N + 1 , 4 ): print (i, end = " " ) print () print ( "Odd: " , 1 , end = " " ) # Print the odd number for i in range ( 4 , N + 1 , 4 ): print (i - 1 , end = " " ) if (N % 4 = = 2 ): print (N + 1 ) elif (N % 4 = = 3 ): print (N) # Driver Code N = 6 evenOddBitwiseXOR(N) # This code is contributed by sanjoy_62 |
C#
// C# program for the above approach using System; class GFG{ // Print all distinct even & odd // prefix Bitwise XORs from 1 to N static void evenOddBitwiseXOR( int N) { Console.Write( "Even: " + 0 + " " ); // Print the even number for ( int i = 4; i <= N; i = i + 4) { Console.Write(i + " " ); } Console.Write( "\n" ); Console.Write( "Odd: " + 1 + " " ); // Print the odd number for ( int i = 4; i <= N; i = i + 4) { Console.Write(i - 1 + " " ); } if (N % 4 == 2) Console.Write(N + 1); else if (N % 4 == 3) Console.Write(N); } // Driver code public static void Main() { int N = 6; evenOddBitwiseXOR(N); } } // This code is contributed by splevel62 |
Javascript
<script> // Javascript implementation of the above approach // Print all distinct even & odd // prefix Bitwise XORs from 1 to N function evenOddBitwiseXOR(N) { document.write( "Even: " + 0 + " " ); // Print the even number for (let i = 4; i <= N; i = i + 4) { document.write(i + " " ); } document.write( "<br/>" ); document.write( "Odd: " + 1 + " " ); // Print the odd number for (let i = 4; i <= N; i = i + 4) { document.write(i - 1 + " " ); } if (N % 4 == 2) document.write(N + 1); else if (N % 4 == 3) document.write(N); } // Driver Code let N = 6; evenOddBitwiseXOR(N); </script> |
Even: 0 4 Odd: 1 3 7
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!