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

×

BIGOF03-Editorial

Problem Link :

Contest
Practice

Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :

easy

Pre-requisite

simple math

Problem :

Given a set of numbers from 0 to n (both inclusive), you have to find a pair of number with maximum XOR and print the maximum XOR value.

Explanation

XOR of two bits is 1 if they are different, otherwise it's zero. In order to maximize XOR, we must ensure that the two numbers have as many bits different at a given position as possible. Since the list is sequencial and is starting from 0, we cannot have a number whose Most Significant Bit is higher than that of 'n'. So, we find the positions of 'n' where it is 1, and create a number with those bits set to zero and vice-versa, i.e. if n=1001101 we find the other number as x=0110010 Now this number is less than 'n' and is bound to be inside the list. The XOR of the numbers is 1111111. From this we can see, the result of the XOR operation is all 1 and where number of 1 is number of bits in 'n'. If n already contains all 1, we can simply XOR it with 0. Pseudo code : int ans=0,pow=1; while(n) { ans+=pow; pow<<=1; n>>=1; }
setter solution
This question is marked "community wiki".

asked 01 May '15, 15:08

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

edited 09 May '15, 15:34

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:

×15,678
×281
×14
×3

question asked: 01 May '15, 15:08

question was seen: 439 times

last updated: 09 May '15, 15:34