All problems

Piano Practice Minutes

Easy · recursion

Mina is learning the piano. On the first day she practises for n minutes. Every day after that she practises for half as long as the day before, rounded down to a whole number of minutes. She stops as soon as a day would come to 0 minutes.

For example, if she starts with 7 minutes, her days are 7, 3 and 1 minutes (half of 1 rounds down to 0, so she stops).

Given n, return the total number of minutes she practises over all her days.

Examples

Example 1

Input: n = 20

Output: 38

Her days are 20, 10, 5, 2 and 1 minutes, and 20 + 10 + 5 + 2 + 1 = 38.

Example 2

Input: n = 7

Output: 11

Her days are 7, 3 and 1 minutes.

Example 3

Input: n = 1

Output: 1

One minute on the first day, then the next day would be 0, so she stops.

Constraints