COLCAND - Editorial - TWZT20TS

PROBLEM LINK:

Practice

Author: Piyush
Tester: Vishal Sharma
Editorialist: Piyush

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Understanding of Bitwise XOR

PROBLEM:

There are some colored muffins. All colors are present in even numbers except for one color. Find the color which has odd colored muffins.

QUICK EXPLANATION:

Since only on color is odd numbers, we can XOR all the numbers and get the odd one out.

EXPLANATION:

Firstly lets go through the concept of bitwise XOR.

If a number is XORed with itself, it vanishes (i.e. becomes zero) : a ^ a = 0

So if there are even numbered a, all XORed will give a 0. And if it occurs odd number of times, the equation will look something like this:

a ^ a ^ a = 0 ^ a = a

So the odd numbered numbers will remain. And since we have just one number which is present in odd quantity, we can use this method to find that number, just XOR all the numbers !

The array A contains N elements where i^{th} element repreents the color of i^{th} muffin.

So our answer is all the numbers XORed.

Time complexity : O(N)

Space Complexity: O(1)

ALTERNATE EXPLANATION:

Since this question was meant to be a very easy one, it was also accepted that you just memorize the count of all numbers in a map and then return the number with odd occurence.

Time Complexity: O(N)

Space Complexity: O(N)

SOLUTIONS:

Setter's Solution
#include<iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int ret = 0;
    while(n--) {
        int a;
        cin>>a;
        ret^=a;
    }
    cout<<ret<<endl;
}