Check whether XOR of all numbers in a given range is even or odd

0 0 6 minutes read

Given a range [ L, R ], the task is to find if the value of XOR of all natural numbers in the range L to R ( both inclusive ) is even or odd. Print ‘Even’ if XOR of all numbers in the range is even, otherwise print odd.

Examples:

Input: L = 1, R= 10 
Output: Odd

Input: L= 5, R=15
Output: Even

A Simple Solution is to calculate XOR of all numbers in range [L, R] and then check if resultant XOR value is even or odd.

C++

// C++ program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if XOR of all numbers
// in range [L, R] is Even or Odd
 
string isEvenOrOdd(int L, int R)
{
    int xorr = 0;
 
    for (int i = L; i <= R; i++) {
        xorr ^= i;
    }
    return ((xorr % 2 == 0) ? "Even" : "Odd");
}
 
// Driver Code
int main()
{
 
    int L = 5, R = 15;
 
    cout << isEvenOrOdd(L, R);
 
    return 0;
}

Java

import java.io.*;
 
class Gfg {
 
    public static String isEvenOrOdd(int L, int R)
    {
        int xorr = 0;
 
        for (int i = L; i <= R; i++) {
            xorr ^= i;
        }
        return ((xorr % 2 == 0) ? "Even" : "Odd");
    }
 
    public static void main(String[] args)
    {
        int L = 5, R = 15;
 
        System.out.println(isEvenOrOdd(L, R));
    }
}

Python3

# Python program to check if XOR of
# all numbers in range [L, R]
# is Even or odd
 
# Function to check if XOR of all numbers
# in range [L, R] is Even or Odd
def isEvenOrOdd( L,  R):
    xorr = 0;
 
    for i in range(L, R+1):
        xorr ^= i;
    if (xorr % 2 == 0):
        return "Even";
    else:
        return "Odd";
 
 
# Driver Code
L = 5;
R = 15;
 
print(isEvenOrOdd(L, R));
 
# This code is contributed by poojaagrawal2.

C#

using System;
 
class Gfg {
  public static string isEvenOrOdd(int L, int R)
  {
    int xorr = 0;
 
    for (int i = L; i <= R; i++) {
      xorr ^= i;
    }
    return ((xorr % 2 == 0) ? "Even" : "Odd");
  }
 
  public static void Main(string[] args)
  {
    int L = 5, R = 15;
 
    Console.WriteLine(isEvenOrOdd(L, R));
  }
}
 
// This code is contributed by divya_p123.

Javascript

// Javascript program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
// Function to check if XOR of all numbers
// in range [L, R] is Even or Odd
function isEvenOrOdd(L, R)
{
    let xorr = 0;
 
    for (let i = L; i <= R; i++) {
        xorr ^= i;
    }
    return ((xorr % 2 == 0) ? "Even" : "Odd");
}
 
// Driver Code
let L = 5, R = 15;
console.log(isEvenOrOdd(L, R));
 
 // This code is contributed by agrawalpoojaa976.

Output

Even

Time Complexity: O(R – L)
Auxiliary Space: O(1)

An Efficient Solution is based on the below fact:

odd ^ odd = even
odd ^ even = odd
even ^ odd = odd
even ^ even = even

XOR of all even numbers will be even ( irrespective of size of range ) and if count of odd numbers is odd then the final XOR will be odd and if even then final XOR will be even.
Now, it can be concluded that,

If the count of Odd Numbers is even,
XOR of all odd numbers = Even
XOR of all even numbers = Even
Final XOR = Even ^ Even = Even

If the count of Odd Numbers is Odd,
XOR of all odd numbers = Odd
XOR of all even numbers = Even
Final XOR = Odd ^ Even = Odd

So, all we have to do is to count odd numbers in range L to R.

Approach :

Count the odd numbers in the range [ L, R ].
Check if count of odd numbers is even or odd.
Print ‘Even’ if count is even otherwise print ‘Odd’ .

Below is the implementation of above approach:

C++

// C++ program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if XOR of all numbers
// in range [L, R] is Even or Odd
 
string isEvenOrOdd(int L, int R)
{
    // Count odd Numbers in range [L, R]
    int oddCount = (R - L) / 2;
 
    if (R % 2 == 1 || L % 2 == 1)
        oddCount++;
 
    // Check if count of odd Numbers
    // is even or odd
 
    if (oddCount % 2 == 0)
        return "Even";
    else
        return "Odd";
}
 
// Driver Code
int main()
{
 
    int L = 5, R = 15;
 
    cout << isEvenOrOdd(L, R);
 
    return 0;
}

Java

// Java program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
class GFG {
 
    // Function to check if XOR of all numbers
    // in range [L, R] is Even or Odd
 
    static String isEvenOrOdd(int L, int R)
    {
        // Count odd Numbers in range [L, R]
        int oddCount = (R - L) / 2;
 
        if (R % 2 == 1 || L % 2 == 1)
            oddCount++;
 
        // Check if count of odd Numbers
        // is even or odd
 
        if (oddCount % 2 == 0)
            return "Even";
        else
            return "Odd";
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int L = 5, R = 15;
 
        System.out.println(isEvenOrOdd(L, R));
    }
}

C#

// C# program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
using System;
class GFG {
 
    // Function to check if XOR of all numbers
    // in range [L, R] is Even or Odd
 
    static string isEvenOrOdd(int L, int R)
    {
        // Count odd Numbers in range [L, R]
        int oddCount = (R - L) / 2;
 
        if (R % 2 == 1 || L % 2 == 1)
            oddCount++;
 
        // Check if count of odd Numbers
        // is even or odd
 
        if (oddCount % 2 == 0)
            return "Even";
        else
            return "Odd";
    }
 
    // Driver Code
    public static void Main()
    {
 
        int L = 5, R = 15;
 
        Console.WriteLine(isEvenOrOdd(L, R));
    }
}

Python3

# Python3 program to check if XOR of
# all numbers in range [L, R] 
# is Even or odd
 
 
# Function to check if XOR of all numbers
# in range [L, R] is Even or Odd
 
def isEvenOrOdd( L, R ):
 
    # Count odd Numbers in range [L, R]
    oddCount = (R - L )/2
     
    if( R % 2 == 1 or L % 2 == 1):
        oddCount = oddCount + 1
     
     
    # Check if count of odd Numbers
    # is even or odd
     
    if(oddCount % 2 == 0 ):
        return "Even"
    else :
        return "Odd"
         
 
     
# Driver Code
 
L = 5
R = 15
 
print(isEvenOrOdd(L, R));

PHP

<?php
// PHP program to check if XOR of all 
// numbers in range [L, R] is Even or odd 
 
// Function to check if XOR of all numbers 
// in range [L, R] is Even or Odd 
function isEvenOrOdd($L, $R) 
{ 
    // Count odd Numbers in range [L, R] 
    $oddCount = floor(($R - $L) / 2); 
 
    if ($R % 2 == 1 || $L % 2 == 1) 
        $oddCount++; 
 
    // Check if count of odd Numbers 
    // is even or odd 
    if ($oddCount % 2 == 0) 
        return "Even"; 
    else
        return "Odd"; 
} 
 
// Driver Code 
$L = 5;
$R = 15; 
 
echo isEvenOrOdd($L, $R); 
 
// This code is contributed by Ryuga
?>

Javascript

<script>
// JavaScript program to check if XOR of 
// all numbers in range [L, R] 
// is Even or odd 
 
 
// Function to check if XOR of all numbers 
// in range [L, R] is Even or Odd 
 
function isEvenOrOdd(L, R) 
{ 
    // Count odd Numbers in range [L, R] 
    let oddCount = Math.floor((R - L) / 2); 
 
    if (R % 2 == 1 || L % 2 == 1) 
        oddCount++; 
 
    // Check if count of odd Numbers 
    // is even or odd 
 
    if (oddCount % 2 == 0) 
        return "Even"; 
    else
        return "Odd"; 
} 
 
// Driver Code 
 
    let L = 5, R = 15; 
 
    document.write(isEvenOrOdd(L, R)); 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Output

Even

Time Complexity : O(1), since there is no loop or recursion.
Auxiliary Space : O(1), since no extra space has been taken.

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 zambiatek!