DEV Community

Ayan Banerjee
Ayan Banerjee

Posted on • Originally published at notescs.gitlab.io on

Maximum Height When Coins are Arranged in Staircase Fashion - A GoDaddy Interview Question

Given a total of n coins find the total number of full staircase rows that can be built.

Staircase rows are those where i-th row has i coins.

For example, given n = 6, return 3 as you can form staircase like this:

*
* *
* * *
Enter fullscreen mode Exit fullscreen mode

Given n = 9, return 3.

*
* *
* * *
* * *
Enter fullscreen mode Exit fullscreen mode

Note that, the 4th row is invalid as it doesn't have 4 coins.

Approach - 1: Binary Search

To build a staircase till k-th row, we need:

1 + 2 + 3 + ... + k = k*(k + 1) / 2 coins.

So we need to find maximum k such that, k*(k + 1) / 2 <= n.

Since n is an increasing function of k, we can use binary search to solve this problem.

We initialize low and high as 0 and n respectively. In each step, we calculate
the value of coins required using the formula n = k*(k + 1) / 2 where k is the
middle element between low and high. If the required coins are greater than
n the value of high is updated to k - 1 and if its less than n, the value
of low is updated to k + 1. Since we reduce the search space by half at each
iteration, the time complexity is O(logN), where N is the number of coins.

C++ code:

#include <iostream>
using namespace std;

int arrangeCoins(int n) {
    long low = 0, high = n;
    while (low <= high) {
        long k = low + (high - low) / 2;
        long cur = k * (k + 1) / 2;

        if (cur == n) return (int)k;

        if (n < cur) {
            high = k - 1;
        } else {
            low = k + 1;
        }
    }
    return (int)high;
}

int main() {
    cout << 6 << " " << arrangeCoins(6) << endl;
    cout << 9 << " " << arrangeCoins(9) << endl;
}
Enter fullscreen mode Exit fullscreen mode

Python code:

def arrangeCoins(n):
    low = 0
    high = n
    while low <= high:
        k = low + (high - low) // 2
        cur = k * (k + 1) // 2

        if cur == n: return k

        if n < cur:
            high = k - 1
        else:
            low = k + 1
    return high

if __name__ == '__main__':
    print(6, arrangeCoins(6))  # n = 6, prints 3
    print(9, arrangeCoins(9))  # n = 9, prints 3
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(logN) due to binary search

Space Complexity: O(1)

Approach - 2: Math

We have formulated the equation:

k*(k + 1) / 2 <= n
k^2 + k <= 2*n
k^2 + k - 2*n <=0
Enter fullscreen mode Exit fullscreen mode

We can use Sridharacarya's formula to solve this equation:

k = (-1 + sqrt(1 + 8n))/2
Enter fullscreen mode Exit fullscreen mode

C++ code:

#include <iostream>
#include <cmath>
using namespace std;

int arrangeCoins(int n) {
    int(-1 + sqrt(1 + (long)8 * n)) / 2;
}

int main() {
    cout << 6 << " " << arrangeCoins(6) << endl;
    cout << 9 << " " << arrangeCoins(9) << endl;
}
Enter fullscreen mode Exit fullscreen mode

Python code:

def arrangeCoins(n):
    return int((-1 + ((1 + 8 * n) ** 0.5)) / 2)

if __name__ == '__main__':
    print(6, arrangeCoins(6))  # n = 6, prints 3
    print(9, arrangeCoins(9))  # n = 9, prints 3
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(1)

Space Complexity: O(1)

Top comments (4)

Collapse
 
10xlearner profile image
10x learner

Nice article 😃

I have one suggestion if you want your C++ solution to be more performant, you can use the keyword constexpr and have your function arrangeCoins to be executed at compile Time 😉

Collapse
 
ayanb profile image
Ayan Banerjee • Edited

Thanks! I will look into it more!

Collapse
 
snej profile image
Jens Alfke • Edited

This is just a simple high-school algebra problem. People really ask this in programming interviews?

If I were asking someone this, I'd react pretty negatively to the binary-search solution -- any competent engineer should realize there's a simple closed-form solution.

Collapse
 
ayanb profile image
Ayan Banerjee

It's an easy question though. Can be asked in phone screen or as a warm up question.