Problem Description

Si the JieJie has too much money. Today, he is feeling rich and carried $B as pocket money to school.

As he is too rich, he wants to feel poorer by converting his money into as few notes as possible and needs your help.

In the Jiejie world, notes comes in denomations of powers of 2. (Eg: $1, $2, $4, $8, $16, $32 .. etc)


A single integer, B, denoting how much money Si the JieJie brought to school today.

It is guaranteed that B will fit into a 64-bit unsigned integer.


A single integer, denoting the minimum number of notes required to express $B in notes.

Sample Input


Sample Output


Explanation for Sample Testcase

19 can be expressed as 16 + 2 + 1 for a minimum of 3 notes.

Submitting .cpp to 'binarycoins'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100