Calculate XOR from 1 to n
The problem is to calculate the XOR of all numbers from 1 to a given integer 'n'. XOR (exclusive OR) is a bitwise operation that outputs 1 if the corresponding bits of its operands are different, otherwise 0. For example, 2 XOR 3 yields 1 because the binary representation of 2 is 0010, and 3 is 0011, so their XOR is 0001.
Problem Statement
Given an integer 'n', we need to calculate the XOR of all integers from 1 to 'n'. For instance, if n=4, we need to compute 1 XOR 2 XOR 3 XOR 4.
Example: Let's consider the case when n=4.
- XOR (1 to 4) = 1 XOR 2 XOR 3 XOR 4 = (1 XOR 2) XOR (3 XOR 4) = 3 XOR 7 = 4
Standard Pseudocode:
function calculateXor(num):
if num < 1:
return
result = 1
counter = 2
while counter <= num:
result = result XOR counter
counter = counter + 1
print("XOR (1 to", num, ") is:", result)
Algorithm Explanation
- Start the function
calculateXor
with the input parameter 'num'. - Check if the input number 'num' is less than 1, if yes, return from the function as XOR cannot be calculated for numbers less than 1.
- Initialize the variable
result
to 1. This will be our final XOR result. - Initialize the variable
counter
to 2. It will be used to loop through numbers from 2 to 'num'. - Enter a while loop that continues as long as 'counter' is less than or equal to 'num'.
- Perform the XOR operation between the current
result
andcounter
and updateresult
with the result of the XOR operation. - Increment the
counter
by 1 to consider the next number in the sequence. - After the loop ends, the variable
result
holds the XOR of all numbers from 1 to 'num'. - Display the calculated XOR result.
Code Solution
Here given code implementation process.
// C Program
// Calculate XOR from 1 to n
#include <stdio.h>
// Calculate xor from 1 to n numbers
void calculateXor(int num)
{
if (num < 1)
{
return;
}
// First number
int result = 1;
// Second number
int counter = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter++;
}
//Display the calculated xor result
printf("\n XOR (1 to %d) is : %d", num, result);
}
int main(int argc, char
const *argv[])
{
// Test Case
calculateXor(4);
calculateXor(10);
calculateXor(13);
calculateXor(16);
calculateXor(19);
return 0;
}
Output
XOR (1 to 4) is : 4
XOR (1 to 10) is : 11
XOR (1 to 13) is : 1
XOR (1 to 16) is : 16
XOR (1 to 19) is : 0
/*
Java program
Calculate XOR from 1 to n
*/
public class XorOperation
{
// Calculate xor from 1 to n numbers
public void calculateXor(int num)
{
if (num < 1)
{
return;
}
// First number
int result = 1;
// Second number
int counter = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter++;
}
//Display the calculated xor result
System.out.print("\n XOR ( 1 to " + num + " ) is : " + result);
}
public static void main(String[] args)
{
XorOperation task = new XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
}
}
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Calculate XOR from 1 to n
*/
class XorOperation
{
public:
// Calculate xor from 1 to n numbers
void calculateXor(int num)
{
if (num < 1)
{
return;
}
// First number
int result = 1;
// Second number
int counter = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter = counter + 1;
}
//Display the calculated xor result
cout << "\n XOR ( 1 to " << num << " ) is : " << result;
}
};
int main()
{
XorOperation task = XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
return 0;
}
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
// Include namespace system
using System;
/*
C# program
Calculate XOR from 1 to n
*/
public class XorOperation
{
// Calculate xor from 1 to n numbers
public void calculateXor(int num)
{
if (num < 1)
{
return;
}
// First number
int result = 1;
// Second number
int counter = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter = counter + 1;
}
//Display the calculated xor result
Console.Write("\n XOR ( 1 to " + num + " ) is : " + result);
}
public static void Main(String[] args)
{
XorOperation task = new XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
}
}
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
<?php
/*
Php program
Calculate XOR from 1 to n
*/
class XorOperation
{
// Calculate xor from 1 to n numbers
public function calculateXor($num)
{
if ($num < 1)
{
return;
}
// First number
$result = 1;
// Second number
$counter = 2;
// Execute loop through by num
while ($counter <= $num)
{
// Do xor operation
$result = $result ^ $counter;
// next number
$counter = $counter + 1;
}
//Display the calculated xor result
echo "\n XOR ( 1 to ". $num ." ) is : ". $result;
}
}
function main()
{
$task = new XorOperation();
// Test Case
$task->calculateXor(4);
$task->calculateXor(10);
$task->calculateXor(13);
$task->calculateXor(16);
$task->calculateXor(19);
}
main();
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
/*
Node Js program
Calculate XOR from 1 to n
*/
class XorOperation
{
// Calculate xor from 1 to n numbers
calculateXor(num)
{
if (num < 1)
{
return;
}
// First number
var result = 1;
// Second number
var counter = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter = counter + 1;
}
//Display the calculated xor result
process.stdout.write("\n XOR ( 1 to " + num + " ) is : " + result);
}
}
function main()
{
var task = new XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
}
main();
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
# Python 3 program
# Calculate XOR from 1 to n
class XorOperation :
# Calculate xor from 1 to n numbers
def calculateXor(self, num) :
if (num < 1) :
return
# First number
result = 1
# Second number
counter = 2
# Execute loop through by num
while (counter <= num) :
# Do xor operation
result = result ^ counter
# next number
counter = counter + 1
# Display the calculated xor result
print("\n XOR ( 1 to ", num ," ) is : ", result, end = "")
def main() :
task = XorOperation()
# Test Case
task.calculateXor(4)
task.calculateXor(10)
task.calculateXor(13)
task.calculateXor(16)
task.calculateXor(19)
if __name__ == "__main__": main()
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
# Ruby program
# Calculate XOR from 1 to n
class XorOperation
# Calculate xor from 1 to n numbers
def calculateXor(num)
if (num < 1)
return
end
# First number
result = 1
# Second number
counter = 2
# Execute loop through by num
while (counter <= num)
# Do xor operation
result = result ^ counter
# next number
counter = counter + 1
end
# Display the calculated xor result
print("\n XOR ( 1 to ", num ," ) is : ", result)
end
end
def main()
task = XorOperation.new()
# Test Case
task.calculateXor(4)
task.calculateXor(10)
task.calculateXor(13)
task.calculateXor(16)
task.calculateXor(19)
end
main()
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
/*
Scala program
Calculate XOR from 1 to n
*/
class XorOperation
{
// Calculate xor from 1 to n numbers
def calculateXor(num: Int): Unit = {
if (num < 1)
{
return;
}
// First number
var result: Int = 1;
// Second number
var counter: Int = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter = counter + 1;
}
//Display the calculated xor result
print("\n XOR ( 1 to " + num + " ) is : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: XorOperation = new XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
}
}
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
/*
Swift 4 program
Calculate XOR from 1 to n
*/
class XorOperation
{
// Calculate xor from 1 to n numbers
func calculateXor(_ num: Int)
{
if (num < 1)
{
return;
}
// First number
var result: Int = 1;
// Second number
var counter: Int = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result ^ counter;
// next number
counter = counter + 1;
}
//Display the calculated xor result
print("\n XOR ( 1 to ", num ," ) is : ", result, terminator: "");
}
}
func main()
{
let task: XorOperation = XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
}
main();
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
/*
Kotlin program
Calculate XOR from 1 to n
*/
class XorOperation
{
// Calculate xor from 1 to n numbers
fun calculateXor(num: Int): Unit
{
if (num < 1)
{
return;
}
// First number
var result: Int = 1;
// Second number
var counter: Int = 2;
// Execute loop through by num
while (counter <= num)
{
// Do xor operation
result = result xor counter;
// next number
counter = counter + 1;
}
//Display the calculated xor result
print("\n XOR ( 1 to " + num + " ) is : " + result);
}
}
fun main(args: Array < String > ): Unit
{
var task: XorOperation = XorOperation();
// Test Case
task.calculateXor(4);
task.calculateXor(10);
task.calculateXor(13);
task.calculateXor(16);
task.calculateXor(19);
}
Output
XOR ( 1 to 4 ) is : 4
XOR ( 1 to 10 ) is : 11
XOR ( 1 to 13 ) is : 1
XOR ( 1 to 16 ) is : 16
XOR ( 1 to 19 ) is : 0
Output Explanation
The provided code uses the calculateXor
function to calculate and display the XOR of all numbers from 1
to the given 'num' for several test cases (num=4, num=10, num=13, num=16, num=19).
Resultant Output
- XOR (1 to 4) is : 4
- XOR (1 to 10) is : 11
- XOR (1 to 13) is : 1
- XOR (1 to 16) is : 16
- XOR (1 to 19) is : 0
Time Complexity
The time complexity of the provided code is O(n) because the while loop runs 'n-1' times, where 'n' is the input number. Each iteration involves a constant-time XOR operation. Therefore, the time complexity is linear in terms of the input 'n'.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment