GFSSOC '15 Winter S1 - OR-deal

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type

One of ButaneBot's intended functions is to perform an OR-sum on a large range of numbers. More specifically, ButaneBot should be able to read in a number N, compute 1 \mathbin{|} 2 \mathbin{|} \dots \mathbin{|} N, and output that number in base 2. However, whenever ButaneBot tries to execute his OR-sum function, he malfunctions and explodes. Can you help ButaneBot by recoding this function?

Reminder: A bitwise OR takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, and otherwise the result is 1.

For example

    0101 (decimal 5)
 OR 0011 (decimal 3)
  = 0111 (decimal 7)

Input Specification

The only line of input will contain a single integer N.


Subtask 1 [40%]

N \le 500\,000\,000

Subtask 2 [60%]

N \le 10^{10}

Output Specification

Output the OR-sum from 1 to N as a binary number.

Sample Input


Sample Output


Explanation for Sample Output

The OR-sum from 1 to 1 is simply 1. 1 in binary is once again 1.

Note: The input will overflow an integer in some languages.


  • 6
    discoverMe  commented on March 18, 2018, 12:09 a.m.

    the input is in base 10 btw