408747: GYM103294 B Lifting Stones

Hercules is bored today. As he does when he is bored, he runs off into the forest to frolic around. Today, he stumbled upon a bunch of very peculiar stones. He found the lightest stone, and then noticed that for every stone except for the smallest stone, there existed another stone that was exactly half its weight, and no two stones had the same weight. Let $$$w$$$ be the weight of the lightest stone. Hercules wants to verify that he can to pick up a weight of $$$n \cdot w$$$, so he selects some subset of the stones to add up to $$$n \cdot w$$$, which is guaranteed to exist and be unique. Given $$$n$$$, determine how many stones Hercules lifted to determine that he could indeed lift a weight of $$$n \cdot w$$$.

The first line of the input will contain $$$n (1 \le n \le 10^9)$$$, the weight in terms of the lightest stone that Hercules can lift.

A single integer detailing the number of stones Hercules lifted to get a weight of $$$n$$$ times the lightest stone.

6

2

For a weight of $$$6w$$$, Hercules lifted stones with weights $$$2w$$$ and $$$4w$$$ for a total weight of $$$6w$$$, which is $$$2$$$ stones.