Every day this month I’ll be documenting my progress through Leetcode’s July Challenge. The month started off with a problem that I really enjoyed, Arranging Coins. The problem, generally stated, is to take a given number of “coins” and stack them into increasing steps such that each subsequent step is incremented by one coin, forming the maximum set of valid steps from the given quantity of coins. Such as, given seven coins, we would build:

graph BT; 1((1)) 2((2)) --- 3((3)); 4((4)) --- 5((5)); 5((5)) --- 6((6)); 7((7));

Here we can see that it is possible to build three valid steps with six coins, having one surplus coin which is insufficient to build another step. This is pretty straightforward and translates easily to a naive algorithm where we increment a step count on each iteration and add that value to total coins used until that value would exceed the available coins. This approach has an asymptotic runtime O(n). This is a pretty good approach, but it can be improved.

The key to a more efficient algorithm for this problem is recognizing that the total coins for any number of valid steps is it’s corresponding triangular number–given an equilateral triangle of side length n, discrete units objects arranged in the object is given by the formula: $$Coins_n = \frac{n(n+1)}{2}$$ which is interestingly also the formula for calculating the sum of natural number from 1 to n. But back to the code.

Having this equation in hand allows us to determine the number of coins needed, $Coins_n$ for a given number of steps, $n$, in a non-linear way–not relying on previous values to determine the current value. This immediatly brings to mind the possibility of using a search algorithm, where the range of values from 1 to the total available coins–admittedly, we could pick a more reasonable endpoint–can be considered an ordered input. This seems like a great opportunity to practice implementing a binary search. On each iteratation of the binary search we’ll check whether the midpoint, representing a given number of steps, requires less, more, or the exact number of coins available. If the number of coins isn’t equal to a specific triangular number, we’ll have some left over. For that case, we’ll return the number of steps one less the number of steps that has an unfilled step. This approach has the asymptotic complexity of most binary search algorithms, O(log n). Let’s see the code:

int arrangeCoins(int n) {
   // sum(1...n) = (n(n+1)) / 2
   int left = 0, right = n;
   while(left <= right) {
	  long steps = left + (right - left) / 2;
	  long coins = (steps*(steps+1))/2;
	  if(coins == n) {
		 return steps;
	  }
	  if(coins < n) {
		 left = steps+1;
	  }
	  else {
		 right = steps-1;
	  }
   }
   return right;
}

This was a great start to the monthly code challenge. Check back for my ongoing posts on each days problem, posted the following day.