Skip to main content

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

  1. Start the function calculateXor with the input parameter 'num'.
  2. 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.
  3. Initialize the variable result to 1. This will be our final XOR result.
  4. Initialize the variable counter to 2. It will be used to loop through numbers from 2 to 'num'.
  5. Enter a while loop that continues as long as 'counter' is less than or equal to 'num'.
  6. Perform the XOR operation between the current result and counter and update result with the result of the XOR operation.
  7. Increment the counter by 1 to consider the next number in the sequence.
  8. After the loop ends, the variable result holds the XOR of all numbers from 1 to 'num'.
  9. 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'.

Last updated on by Kalkicode




Comment

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