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 = 7ans = 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 |
Output
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> |
Output
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
This article is contributed by Sahil Chhabra. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
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!
