Given an integer N, the task is to find the Bitwise XOR of all odd numbers in the range [1, N].
Examples:
Input: 11
Output: 2
Explanation: Bitwise XOR of all odd numbers up to 11 = 1 ^ 3 ^ 5 ^ 7 ^ 9 ^ 11 = 2.Input: 10
Output: 9
Explanation: Bitwise XOR of all odd numbers up to 10 = 1 ^ 3 ^ 5 ^ 7 ^ 9 = 9.
Naive Approach: The simplest approach to solve the problem is to iterate over the range [1, N] and for every value, check if it is odd or not. Calculate Bitwise XOR of every odd element found and print it as the required result.
Below is the implementation of above approach :
C++
// C++ program for the Naive approach#include <bits/stdc++.h>using namespace std;// Function to find the XOR of odd numbers// less than or equal to N using the naive approachvoid findOddXOR(int n){ int xorVal = 0; for (int i = 1; i <= n; i++) { if (i % 2 != 0) { xorVal ^= i; } } // Print the answer cout << xorVal;}// Driver Codeint main(){ int N = 11; // Function Call findOddXOR(N); return 0;} |
Python3
# Python3 program for the Naive approach# Function to find the XOR of odd numbers# less than or equal to N using the naive approachdef findOddXOR(n): xorVal = 0 for i in range(1, n+1): if i % 2 != 0: xorVal ^= i # Print the answer print(xorVal)# Driver CodeN = 11# Function CallfindOddXOR(N) |
Javascript
// Javascript program for the Naive approach// Function to find the XOR of odd numbers// less than or equal to N using the naive approachfunction findOddXOR(n) { let xorVal = 0; for (let i = 1; i <= n; i++) { if (i % 2 !== 0) { xorVal ^= i; } } console.log(xorVal);}// Driver Codeconst N = 11;// Function CallfindOddXOR(N); |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the following formula to calculate Bitwise XOR of all odd numbers less than or equal to N:
Let f(N) = 2 ^ 4 ^ 6 ^ … ^ (N − 2) ^ n and g(n) = 1 ^ 2 ^ 3 ^ … ^ (N − 2) / 2 ^ (N / 2)
=> f(N) = 2 * g(N)Now, let k(N) = 1 ^ 2 ^ 3 ^ … ^ (N − 2) ^ N
XOR of all odd numbers less than or equal to N = k(N) ^ f(N) [Since all even numbers cancel their own bits leaving only odd numbers].
Substituting the value of f(N) = 2 * g(N), XOR of all odd numbers up to N = k(N) ^ (2 * g(N))
Follow the steps below to solve the problem:
- Store XOR of numbers in the range[1, N] in a variable, say K.
- If N is odd, store the XOR of numbers in the range[1, (N – 1) / 2] in a variable, say g. Otherwise, store XOR of numbers in the range[1, N / 2] in g.
- Using the derived formula, update result to K ^ (2 * g).
- After completing the above steps, print the value of the result as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate Bitwise// XOR of odd numbers in the range [1, N]int findXOR(int n){ // N & 3 is equivalent to n % 4 switch (n & 3) { // If n is multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; // If n % 4 gives remainder 3 case 3: return 0; }}// Function to find the XOR of odd// numbers less than or equal to Nvoid findOddXOR(int n){ // If number is even if (n % 2 == 0) // Print the answer cout << ((findXOR(n)) ^ (2 * findXOR(n / 2))); // If number is odd else // Print the answer cout << ((findXOR(n)) ^ (2 * findXOR((n - 1) / 2)));}// Driver Codeint main(){ int N = 11; // Function Call findOddXOR(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to calculate Bitwise // XOR of odd numbers in the range [1, N] static int findXOR(int n) { // N & 3 is equivalent to n % 4 switch (n & 3) { // If n is multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; } // If n % 4 gives remainder 3 return 0; } // Function to find the XOR of odd // numbers less than or equal to N static void findOddXOR(int n) { // If number is even if (n % 2 == 0) // Print the answer System.out.print(((findXOR(n)) ^ (2 * findXOR(n / 2)))); // If number is odd else // Print the answer System.out.print(((findXOR(n)) ^ (2 * findXOR((n - 1) / 2)))); } // Driver Code public static void main(String[] args) { int N = 11; // Function Call findOddXOR(N); }}// This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach# Function to calculate Bitwise# XOR of odd numbers in the range [1, N]def findXOR(n): # N & 3 is equivalent to n % 4 if (n % 4 == 0): # If n is multiple of 4 return n; elif (n % 4 == 1): # If n % 4 gives remainder 1 return 1; # If n % 4 gives remainder 2 elif (n % 4 == 2): return n + 1; # If n % 4 gives remainder 3 elif (n % 4 == 3): return 0;# Function to find the XOR of odd# numbers less than or equal to Ndef findOddXOR(n): # If number is even if (n % 2 == 0): # Print the answer print(((findXOR(n)) ^ (2 * findXOR(n // 2)))); # If number is odd else: # Print the answer print(((findXOR(n)) ^ (2 * findXOR((n - 1) // 2))));# Driver Codeif __name__ == '__main__': N = 11; # Function Call findOddXOR(N);# This code is contributed by 29AjayKumar |
C#
// C# program for the above approachusing System;public class GFG{ // Function to calculate Bitwise // XOR of odd numbers in the range [1, N] static int findXOR(int n) { // N & 3 is equivalent to n % 4 switch (n & 3) { // If n is multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; } // If n % 4 gives remainder 3 return 0; } // Function to find the XOR of odd // numbers less than or equal to N static void findOddXOR(int n) { // If number is even if (n % 2 == 0) // Print the answer Console.Write(((findXOR(n)) ^ (2 * findXOR(n / 2)))); // If number is odd else // Print the answer Console.Write(((findXOR(n)) ^ (2 * findXOR((n - 1) / 2)))); } // Driver Code public static void Main(String[] args) { int N = 11; // Function Call findOddXOR(N); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Function to calculate Bitwise// XOR of odd numbers in the range [1, N]function findXOR(n){ // N & 3 is equivalent to n % 4 switch (n & 3) { // If n is multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; // If n % 4 gives remainder 3 case 3: return 0; }}// Function to find the XOR of odd// numbers less than or equal to Nfunction findOddXOR(n){ // If number is even if (n % 2 == 0) // Print the answer document.write((findXOR(n)) ^ (2 * findXOR(n / 2))); // If number is odd else // Print the answer document.write((findXOR(n)) ^ (2 * findXOR((n - 1) / 2)));}// Driver Code let N = 11; // Function Call findOddXOR(N);// This code is contributed by Surbhi Tyagi.</script> |
Output
2
Time Complexity: O(1)
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!
