kalimm's blog

Good Solution For 440A
By kalimm, 10 years ago, In English

Hi everyone! I have a solution for 440A, and I want to share it.

FOR(i,1,n-1)
    {
        cin >> x;

        t^=x;
        t^=i;
    }

    t^=n;

    cout << t << endl;

The proof is,

x xor x = 0

Make xor to all elements in array, and make xor all number 1 to n. The value is our answer. Because if one number is xor twice, number doesn't change anything.

Sorry for my poor English...

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

i used this exact approach to solve OLOLO on SPOJ. :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another Way , don't know any other people tried this way-

http://codeforces.net/contest/440/submission/6823214

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can visit this entry. Similar problem. http://codeforces.net/blog/entry/12719

→ Reply
»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

i am getting time limit exceeded for spoj prob OLOLO

Y??

include

include

include

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; }

→ Reply