Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

lovro-sinda's blog

By lovro-sinda, 4 years ago, In English,

First I want you to read the task and try to solve it in linear time complexity, and minimum memorize complexity.

Lonely Integer
There are N integers in an array A. All but one integer occurs in pairs. Your task is to find out the number that occurs only once.

Input Format

The first line of the input contains an integer N indicating number of integers in the array A. The next line contains N integers each separated by a single space. Constraints 1 <= N < 100 N % 2 = 1 ( N is an odd number ) 0 <= A[i] <= 100, ∀ i ∈ [1, N]

Output Format

Output S, the number that occurs only once.
Sample Input
3
1 1 2
Sample Output
2

If you don't have any idea I will write a code.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
 	int N;
	cin >> N;
	int tmp, result = 0;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		result ^= tmp;
	}
	cout << result;
    return 0;
}

Cool trick using only xor operation, but I can't prove why that work. Can anyone prove it?

 
 
 
 
  • Vote: I like it  
  • -20
  • Vote: I do not like it  

»
4 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

http://codeforces.com/blog/entry/12534

Same proof with this.

x xor x = 0 So xor all numbers. If a number is xor twice, number doesn't change anything.

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The proof follows from properties of xor:

  1. a^b=b^a

  2. a^a=0

  3. a^0=a

The first one lets us reorder the numbers in any way without the xor being affected. Then, we get the xor as (a^a)^(b^b)^(c^c)^...^(r^r)^s, which is 0^0^0^...^0^s=s.

Also, the linear time complexity is caused by computers being constructed to do bitwise operations in O(1). If you did it on paper, your complexity would be . It's a cool trick nevertheless.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Actually for reodering numbers we need one more property: a^(b^c)=(a^b)^c

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

awesome, can we have more of these ?