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 Oddstring isEvenOrOdd(int L, int R){ int xorr = 0; for (int i = L; i <= R; i++) { xorr ^= i; } return ((xorr % 2 == 0) ? "Even" : "Odd");}// Driver Codeint 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 Odddef isEvenOrOdd( L, R): xorr = 0; for i in range(L, R+1): xorr ^= i; if (xorr % 2 == 0): return "Even"; else: return "Odd";# Driver CodeL = 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 Oddfunction isEvenOrOdd(L, R){ let xorr = 0; for (let i = L; i <= R; i++) { xorr ^= i; } return ((xorr % 2 == 0) ? "Even" : "Odd");}// Driver Codelet 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 Oddstring 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 Codeint 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 oddclass 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 oddusing 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 Odddef 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 CodeL = 5R = 15print(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
