Print all distinct even and odd prefix Bitwise XORs of first N natural numbers

Print all distinct even and odd prefix Bitwise XORs of first N natural numbers

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++

#include <bits/stdc++.h> using namespace std;    void evenOddBitwiseXOR(int N) {        cout << "Even: " << 0 << " ";             for (int i = 4; i <= N; i = i + 4) {         cout << i << " ";     }        cout << "\n";        cout << "Odd: " << 1 << " ";             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; }    int main() {     int N = 6;     evenOddBitwiseXOR(N);        return 0; }

Output:

Even: 0 4 
Odd: 1 3 7

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets