thoughtbook

Thursday, February 23, 2023

Arranging coins

Leetcode 441 problem.

Go

Time complexity: $O(n)$ - n is a parameter number
Auxiliary space: $O(1)$ - constant amount of space

func arrangeCoins(n int) int {
    completeRows := 0

    // first row is 1, i = 1
    for i := 1; i <= n; i++ {
        // if there are still coins after row (i) deduction
        if n - i >= 0 {
            // add row
            completeRows++
            // remove coins of current row from total
            n -= i
        }
    }

    return completeRows
}

Typescript

Time complexity: $O(n)$ - n is a parameter number
Auxiliary space: $O(1)$ - constant amount of space

function arrangeCoins(n: number): number {
  let completeRows = 0;
  let usedCoins = 0;

  for (let i = 1; i <= n; i++) {
    usedCoins += i;

    if (usedCoins <= n) {
      completeRows++;
    } else {
      return completeRows;
    }
  }

  return completeRows;
}