Home » C++ programs

C++ program to Find Nth element of the X-OR sequence

In this C++ program, we will learn how to find the Nth element of the X-OR sequence? Here, we are discussing about two methods 1) Native Method and 2) Efficient Method.
Submitted by Shubham Singh Rajawat, on January 23, 2018

To find the X-OR series there are two methods,

1. Naive method: This is the basic method in which we have to do X-OR of every number and print the last number. It’s complexity is O(n) as we have to traverse the array only once.
2. Efficient method As the X-OR series follows a simple pattern we can just find the result in constant time O(1) time complexity:
   1. Take modulo of n
   2. If remainder is 0 result=n
   3. If remainder is 1 result=1
   4. If remainder is 2 result=n+1
   5. If remainder is 3 result=0

C++ program:



#include <iostream>
using namespace std;

int sequence(int n)
{
	int a;
	switch(n%4)  
	{
		case 0:
			a=n;
			break;    
		case 1: 
			a=1; 
			break;       
		case 2:
			a=n+1;
			break;
		case 3: 
			a=0;
			break;
	}
	return a;
}

//main function
int main(){
	int n;
	//input number
	cin>>n;
	
	int result=sequence(n);
	cout<<result<<endl;
	return 0;
}

Output

First run:
127
0

Second run:
5
1

Explanation:

    Number      X-OR 1 to N     modulo 4

    1           0001            1 (1) 
    2           0011            2 (n+1)
    3           0000            3 (0)
    4           0100            0 (n)
    5           0001            1 (1)
    6           0111            2 (n+1)
    7           0000            3 (0)
    8           1000            0 (n)