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.
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++
#include <bits/stdc++.h>
using namespace std;
string isEvenOrOdd( int L, int R)
{
int xorr = 0;
for ( int i = L; i <= R; i++) {
xorr ^= i;
}
return ((xorr % 2 == 0) ? "Even" : "Odd" );
}
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
def isEvenOrOdd( L, R):
xorr = 0 ;
for i in range (L, R + 1 ):
xorr ^ = i;
if (xorr % 2 = = 0 ):
return "Even" ;
else :
return "Odd" ;
L = 5 ;
R = 15 ;
print (isEvenOrOdd(L, R));
|
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));
}
}
|
Javascript
function isEvenOrOdd(L, R)
{
let xorr = 0;
for (let i = L; i <= R; i++) {
xorr ^= i;
}
return ((xorr % 2 == 0) ? "Even" : "Odd" );
}
let L = 5, R = 15;
console.log(isEvenOrOdd(L, R));
|
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.
- 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++
#include <bits/stdc++.h>
using namespace std;
string isEvenOrOdd( int L, int R)
{
int oddCount = (R - L) / 2;
if (R % 2 == 1 || L % 2 == 1)
oddCount++;
if (oddCount % 2 == 0)
return "Even" ;
else
return "Odd" ;
}
int main()
{
int L = 5, R = 15;
cout << isEvenOrOdd(L, R);
return 0;
}
|
Java
class GFG {
static String isEvenOrOdd( int L, int R)
{
int oddCount = (R - L) / 2 ;
if (R % 2 == 1 || L % 2 == 1 )
oddCount++;
if (oddCount % 2 == 0 )
return "Even" ;
else
return "Odd" ;
}
public static void main(String[] args)
{
int L = 5 , R = 15 ;
System.out.println(isEvenOrOdd(L, R));
}
}
|
C#
using System;
class GFG {
static string isEvenOrOdd( int L, int R)
{
int oddCount = (R - L) / 2;
if (R % 2 == 1 || L % 2 == 1)
oddCount++;
if (oddCount % 2 == 0)
return "Even" ;
else
return "Odd" ;
}
public static void Main()
{
int L = 5, R = 15;
Console.WriteLine(isEvenOrOdd(L, R));
}
}
|
Python3
def isEvenOrOdd( L, R ):
oddCount = (R - L ) / 2
if ( R % 2 = = 1 or L % 2 = = 1 ):
oddCount = oddCount + 1
if (oddCount % 2 = = 0 ):
return "Even"
else :
return "Odd"
L = 5
R = 15
print (isEvenOrOdd(L, R));
|
PHP
<?php
function isEvenOrOdd( $L , $R )
{
$oddCount = floor (( $R - $L ) / 2);
if ( $R % 2 == 1 || $L % 2 == 1)
$oddCount ++;
if ( $oddCount % 2 == 0)
return "Even" ;
else
return "Odd" ;
}
$L = 5;
$R = 15;
echo isEvenOrOdd( $L , $R );
?>
|
Javascript
<script>
function isEvenOrOdd(L, R)
{
let oddCount = Math.floor((R - L) / 2);
if (R % 2 == 1 || L % 2 == 1)
oddCount++;
if (oddCount % 2 == 0)
return "Even" ;
else
return "Odd" ;
}
let L = 5, R = 15;
document.write(isEvenOrOdd(L, R));
</script>
|
Time Complexity : O(1), since there is no loop or recursion.
Auxiliary Space : O(1), since no extra space has been taken.