Little Johnny has a stick that is 64 centimeters long, but he thinks it would be more fun to play with a stick that is x centimeters long. He decides to break the original stick into a number of smaller sticks, and then glue them together to get a stick that is exactly x centimeters long.
The easiest way to break a stick is to break it in half, so Johnny will use the following procedure:
- Sum the lengths of all the sticks (initially, there is just one 64 centimeter stick). While this sum is greater than x, repeat the following:
- Take one of the sticks with the shortest length and break it in half.
- If discarding one of the halves would not make the sum of the remaining sticks' lengths less than x, throw that half away.
- Finally, glue the remaining sticks together to form a stick that is x centimeters long.
Return the number of sticks Johnny would have to glue together in the final step if he follows the above procedure. If he has only one stick when he gets to the final step, return 1 (see example 0).
|