DWITE '10 R4 #3 - Binary Weight - Olympiads Online Judge

DWITE '10 R4 #3 - Binary Weight

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 0.1s

Memory limit: 64M

Problem type

DWITE Online Computer Programming Contest, January 2011, Problem 3

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

The input will contain 5 lines, integers $1 \le N \le 1\,000\,000\,000$ $1 \leq N \leq 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$ $2$ , where $1$ $1$ means that power is included, and $0$ $0$ means that it's not. So a binary $43$ $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$ $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$ $1 \times 32 + 0 \times 16 + 1 \times 8 + 0 \times 4 + 1 \times 2 + 1 \times 2 = 32 + 8 + 2 + 1 = 43$ ( $101011$ $101011$ ).

Sample Input

Copy

Sample Output

Copy

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

2

notpeachay420 commented on Aug. 19, 2020, 7: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, 8: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.