Arranging Coins - Cplusplus

You have a total of n coins and you want to arrange the coins in staircase shape, where every i-th row must have exactly i coins. You want to find the total number of full staircase rows that can be formed.

Example:

Input : n = 7
Output : 3

We can form the staircase as follows :
C
C C
C C C
C
Here only 3 rows are complete

Naive Approch:
This problem can be solved by linear scan.
We can traverse the all the number from 1 while n*(n+1)/2 is less or equal to n where n = 1, 2, 3, …n.
Time complexity of this approach is O(n).

Efficient Approch:
We can solve this problem using binary search.

C++

#include <bits/stdc++.h>
using namespace std;

int findRows(int n)
{
    int l = 0, r = n, mid, k ;

        //finding middle element
        while (l <= r)
        {
            mid = l+(r-l)/2;

            //check condition for mid if true 
            //go to the right part else left part
            if(n >= (mid*(mid+1))/2 )
            {
                k = mid;
                l = mid + 1;
            }
            else
                r=mid - 1;
        }

        return k;
}

// Driver Code 
int main()
{
    int n = 7;

    //calling function
    int k = findRows(n) ;
    cout << k ;
    
  return 0;
}

Python

# Write Python3 code here
def findRows(n):

	l, r = 0, n
	k = 0

	while( l<= r) :

		#finding middle element
		mid = l+(r-l)//2
			
		#check condition for mid if true go to the right part else left part

		if (n >= (mid*(mid+1))//2) :

			l = mid + 1
			k = mid

		else :
			r = mid - 1

	return k


n = 7

#calling function
k = findRows(n)
print(k)

Output:

Time Complexity : O(log n)
Space Complexity : O(1)