Calculate XOR from 1 to n.
Given a number n, the task is to find the XOR from 1 to n.
Examples :
Input : n = 6
Output : 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Input : n = 7
Output : 0
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Method 1 (Naive Approach):
1- Initialize the result as 0.
1- Traverse all numbers from 1 to n.
2- Do XOR of numbers one by one with results.
3- At the end, return the result.
C++
// C++ program to find XOR of numbers // from 1 to n. #include <bits/stdc++.h> using namespace std; int computeXOR( int n) { if (n == 0) return 0; // base case int uni = 0; for ( int i = 1; i <= n; i++) { uni = uni ^ i; // calculate XOR } return uni; } int main() { int n = 7; int result = computeXOR(n); cout << result << endl; return 0; } /* This code is contributed by Rishab Dugar */ |
Java
// Given a number n, find the XOR from 1 to n for given n number import java.io.*; public class GFG { public static void main(String[] args) { int n = 7 ; int ans = computeXor(n); System.out.println(ans); } static int computeXor( int n){ if (n == 0 ) return 0 ; // base case int uni = 0 ; for ( int i = 1 ; i <= n; i++) { uni = uni^i; // calculate XOR } return uni; } } /* This code is contributed by devendra salunke */ |
Python3
#defining a function computeXOR def computeXOR(n): uni = 0 if n = = 0 : return 0 #base case for i in range ( 1 ,n + 1 ): uni = uni ^ i return uni n = 7 ans = computeXOR(n) #calling the function print (ans) #This code is contributed by Gayatri Deshmukh |
C#
// C# program that finds the XOR // from 1 to n for a given number n using System; public class GFG { static int computeXor( int n) { if (n == 0) return 0; // base case int uni = 0; for ( int i = 1; i <= n; i++) { uni = uni ^ i; // calculate XOR } return uni; } // Driver code public static void Main( string [] args) { int n = 7; // Function call int ans = computeXor(n); Console.WriteLine(ans); } } // This code is contributed by phasing17 |
Javascript
// JavaScript that for a number n // finds the XOR from 1 to n for given n number function computeXor(n){ if (n == 0) return 0; // base case var uni = 0; for ( var i = 1; i <= n; i++) uni = uni^i; // calculate XOR return uni; } // Driver Code var n = 7; // Function Call var ans = computeXor(n); console.log(ans); // This code is contributed by phasing17 |
0
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 2 (Efficient method) :
1- Find the remainder of n by moduling it with 4.
2- If rem = 0, then XOR will be same as n.
3- If rem = 1, then XOR will be 1.
4- If rem = 2, then XOR will be n+1.
5- If rem = 3 ,then XOR will be 0.
C++
// C++ program to find XOR of numbers // from 1 to n. #include<bits/stdc++.h> using namespace std; // Method to calculate xor int computeXOR( int n) { // If n is a multiple of 4 if (n % 4 == 0) return n; // If n%4 gives remainder 1 if (n % 4 == 1) return 1; // If n%4 gives remainder 2 if (n % 4 == 2) return n + 1; // If n%4 gives remainder 3 return 0; } // Driver method int main() { int n = 5; cout<<computeXOR(n); } // This code is contributed by rutvik_56. |
Java
// Java program to find XOR of numbers // from 1 to n. class GFG { // Method to calculate xor static int computeXOR( int n) { // If n is a multiple of 4 if (n % 4 == 0 ) return n; // If n%4 gives remainder 1 if (n % 4 == 1 ) return 1 ; // If n%4 gives remainder 2 if (n % 4 == 2 ) return n + 1 ; // If n%4 gives remainder 3 return 0 ; } // Driver method public static void main (String[] args) { int n = 5 ; System.out.println(computeXOR(n)); } } |
Python 3
# Python 3 Program to find # XOR of numbers from 1 to n. # Function to calculate xor def computeXOR(n) : # Modulus operator are expensive # on most of the computers. n & 3 # will be equivalent to n % 4. # if n is multiple of 4 if n % 4 = = 0 : return n # If n % 4 gives remainder 1 if n % 4 = = 1 : return 1 # If n%4 gives remainder 2 if n % 4 = = 2 : return n + 1 # If n%4 gives remainder 3 return 0 # Driver Code if __name__ = = "__main__" : n = 5 # function calling print (computeXOR(n)) # This code is contributed by ANKITRAI1 |
C#
// C# program to find XOR // of numbers from 1 to n. using System; class GFG { // Method to calculate xor static int computeXOR( int n) { // If n is a multiple of 4 if (n % 4 == 0) return n; // If n%4 gives remainder 1 if (n % 4 == 1) return 1; // If n%4 gives remainder 2 if (n % 4 == 2) return n + 1; // If n%4 gives remainder 3 return 0; } // Driver Code static public void Main () { int n = 5; Console.WriteLine(computeXOR(n)); } } // This code is contributed by ajit |
PHP
<?php // PHP program to find XOR // of numbers from 1 to n. // Function to calculate xor function computeXOR( $n ) { // Modulus operator are expensive // on most of the computers. n & 3 // will be equivalent to n % 4. switch ( $n & 3) // n % 4 { // 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; } } // Driver code $n = 5; echo computeXOR( $n ); // This code is contributed by aj_36 ?> |
Javascript
<script> // JavaScript program to find XOR of numbers // from 1 to n. // Function to calculate xor function computeXOR(n) { // Modulus operator are expensive on most of the // computers. n & 3 will be equivalent to n % 4. // if n is multiple of 4 if (n % 4 == 0) return n; // If n % 4 gives remainder 1 if (n % 4 == 1) return 1; // If n % 4 gives remainder 2 if (n % 4 == 2) return n + 1; // If n % 4 gives remainder 3 if (n % 4 == 3) return 0; } // Driver code // your code goes here let n = 5; document.write(computeXOR(n)); // This code is constributed by Surbhi Tyagi. </script> |
1
Time Complexity: O(1)
Auxiliary Space: O(1)
How does this work?
When we do XOR of numbers, we get 0 as the XOR value just before a multiple of 4. This keeps repeating before every multiple of 4.
Number Binary-Repr XOR-from-1-to-n 1 1 [0001] 2 10 [0011] 3 11 [0000] <----- We get a 0 4 100 [0100] <----- Equals to n 5 101 [0001] 6 110 [0111] 7 111 [0000] <----- We get 0 8 1000 [1000] <----- Equals to n 9 1001 [0001] 10 1010 [1011] 11 1011 [0000] <------ We get 0 12 1100 [1100] <------ Equals to n
Contact Us