clueless coding // TODO: be smarter

LeetCode 441. Arranging Coins: C++ Solution



Problem Statement


You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Function Signature (C++):
  int arrangeCoins(int n)

Inputs:
  n = 5

Outputs:
  2

We can create rows like this:
¤
¤ ¤
¤ ¤
There are 2 full rows.

Inputs:
  n = 8

Outputs:
  3

We can create rows like this:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
There are 3 full rows.



TL;DR Code Solution


int arrangeCoins(int n) {

    long left = 1;
    long right = n;

    while (left <= right) {
        long middle = (left + right) / 2;
        long sum = (middle * (middle + 1)) / 2.0;

        if (sum < n) {
            left = middle + 1;
        }
        else if (sum > n) {
            right = middle - 1;
        }
        else {
            return middle;
        }
    }

    return left - 1;

}