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)





Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions


We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.