CODEWITHSUNDEEP
c++arrayssearchoperators
Ashish Siwal
Ashish Siwal

Reputation: 17

How can I do this C++ question by using XOR operator for 2 or more digits number

XOR is working fine for single digit inputs but totally messes up while using 2 or more digits number. How can I still make this program by using XOR ?

This is the question basically :

Find the Missing Number

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

My program is:

#include<iostream>

using namespace std;

int main(void)
{
    int n; //number of elements

    cout << "Enter the number of elements : ";
    cin >> n;

    //Declaring array
    int arr[n-1];

    //Taking input
    for(int i = 0; i<n-1; i++)
    cin >> arr[i];

    //printing array
    cout << "\nElements are :";
    for(int i = 0; i<n-1; i++)
    cout << " " << arr[i];

    //Declaring elements to take XOR
    int x1 = arr[0]; // first element of array
    int x2 = 1; //first element in natural number series i.e 1,2,3,4...

    //taking XOR of all elements of the given array
    for(int i = 1; i<n-1; i++)
    x1 ^= arr[i];

    //taking XOR of all the natural numbers till 'n'
    for(int i = 2; i<arr[n-1]; i++)
    x2 ^= i;

    //Finally printing the output by taking XOR of x1 and x2
    //because same numbers will be removed since (A^A) = 0 also (A^0) = A
    cout << "\nMissing number : " << (x1^x2) << endl;

    return 0;
}

The above program doesn't work for the input below:

10
1 2 3 4 5 6 7 8 10

Upvotes: 0

Views: 259

Answers (1)

Jarod42
Jarod42

Reputation: 217135

Your loops are wrong, you can change to:

//Declaring elements to take XOR
int x1 = 0; // for element of array
int x2 = 0; // for natural number series i.e 1,2,3,4...

//taking XOR of all elements of the given array
for (int i = 0; i < n-1; i++)
    x1 ^= arr[i];

//taking XOR of all the natural numbers till 'n'
for (int i = 1; i != n + 1; i++)
    x2 ^= i;

Note that natural number range is bigger than arr size.

Upvotes: 1

Related Questions