Problem Statement
You have a collection of sticks. The length of each stick is a positive integer.
You want to have a collection of sticks in which all the sticks have the same length. You may alter your current collection by performing zero or more steps. Each step must look as follows:
- You choose one of your sticks. The chosen stick must have length at least 2.
- Let L be the length of the chosen stick.
- If L is even, cut the stick into two sticks of length L/2 each. Otherwise, cut it into sticks of lengths (L-1)/2 and (L+1)/2.
- Keep one of the two new sticks and throw away the other one.
It can be proved that any collection of sticks can be turned into a collection of sticks that all have the same length. You are given the current lengths of your sticks in the int[] a. Compute and return the smallest number of steps needed to reach your goal.
Definition
- Class:
- Halving
- Method:
- minSteps
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int minSteps(int[] a)
- (be sure your method is public)
Constraints
- a will contain between 2 and 50 elements, inclusive.
- Each element of a will be between 1 and 109, inclusive.
Examples
{11, 4}Returns: 3
One optimal solution is: Pick the stick of length 11, cut it into sticks of lengths 5 and 6 and keep the part of length 5. Pick the stick of length 4, cut it into two sticks of length 2 and keep the part of length 2. Pick the stick of length 5, cut it into sticks of lengths 2 and 3 and keep the part of length 2. In the end, you'll have two sticks of length 2.{1000000000, 1000000000, 1000000000, 1000000000}Returns: 0
All your sticks have the same length, no steps are needed.{1, 2, 3, 4, 5, 6, 7}Returns: 10
{13, 13, 7, 11, 13, 11}Returns: 11
{1, 1}Returns: 0