You are not logged in. Please login at www.codechef.com to post your questions!

×

xor of sequence of numbers

You are given with a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. Your goal is to minimize the sum of added numbers.

e.g. Consider the following examples :

sequence : 1, 3 answer : 2, adding 2 to 1 we get 3^3=0.

sequence : 10, 4, 5, 1 answer: 6, adding 3 to 10 & 3 to 8 we get 13^4^8^1 = 0.

sequence : 4, 4 answer : 0, since 4^4 = 0.

I tried working on binary representations of sequence number but it got so complex. I want to know if there is any simple and efficient way to solve this problem.

asked 30 Jun '12, 11:52

argonaut's gravatar image

2★argonaut
9013920
accept rate: 12%

edited 01 Jul '12, 12:24

Please add link, it seems to be interesting problem ;-) My idea is that you do xor for all elements in sequence and then you simply want to eliminate most significant bit in result as first...

(02 Jul '12, 15:16) betlista ♦♦3★

@betlista: If you do xor of all elements you will only get an upper bound of value to be added.

(09 Jul '12, 17:36) argonaut2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,901
×1,470
×303

question asked: 30 Jun '12, 11:52

question was seen: 6,570 times

last updated: 23 Dec '18, 20:08