DWITE '10 R4 #3 - Binary Weight

View as PDF

Submit solution

Points: 5
Time limit: 0.1s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, January 2011, Problem 3

The binary weight of a number is the amount of 1s in the number's binary representation. For example, 43 in binary is 101011, so the binary weight is 4. Given a decimal number, we want to find the next greater decimal number that has the same binary weight. In this case, 45 (101101) is such a number.

The input will contain 5 lines, integers 1 \le N \le 1\,000\,000\,000.

The output will contain 5 lines, each corresponding to the next decimal number with the same binary weight as in the input.

Reminder: a binary representation of a number is the sum of powers of 2, where 1 means that power is included, and 0 means that it's not. So a binary 43 is 1\times 2^5 + 0\times 2^4 + 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0, which evaluates to 1\times 32 + 0\times 16 + 1\times 8 + 0\times 4 + 1\times 2 + 1\times 2 = 32 + 8 + 2 + 1 = 43 (101011).

Sample Input

3
4
10
7
8

Sample Output

5
8
12
11
16

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments


  • 1
    notpeachay420  commented on Aug. 19, 2020, 3:20 p.m. edit 3

    can someone pls give me tips on how to make my code run faster?


    • 6
      Tzak  commented on Aug. 19, 2020, 4:25 p.m.

      Your complexity is too slow, consider asking your code nicely to run faster or observe what happens with the binary representations of the numbers.