let's submit our answer:

How to be a creative thinker | Carnegie Mellon University Po-Shen Loh

441. Arranging Coins #binary_search #Easy #leet_code_Q8 #441

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3

You can contact me if you have any comments, ideas, questions, or anything to talk about https://news.1rj.ru/str/zprogramming_bot

let's solve the question.

First, how can we determine the number of coins that are enough for building an n-staircase? Let's look at an example: to build 1 stair, we need 1 coin; for 2 stairs, we need 3 coins; for 3 stairs, we need 5 coins; and for 4 stairs, we need 10 coins. What do you notice from this pattern? The number of stairs and the number of coins have a relationship, so we can use the formula (n+1 * n) / 2 to calculate the number of coins needed based on the number of stairs.

Let's say n is the number of stairs and c is the number of coins. Based on this, we can iterate from 1 up to n, where (n+1 * n) / 2 > c. When we find the first n that fulfills this condition, we subtract 1 so that n is the maximum number of stairs that we can build with the given number of coins.

But since it has O(N) time complexity, we need to find a more efficient approach. This is where binary search comes in handy. By using binary search with left = 1 and right = the number of coins, we can cut the array size in half each time and find the answer with O(logN) time complexity.

let's write the code and submit.

Approach 1 : using Brute Force Method Answer :

 class Solution:
    def arrangeCoins(self, n: int) -> int i =  1
          while (True):
            total =( (i) * (i + 1) )/ 2
            if total > n:
                return i-1:
           else:  i+=1

Approach 2: using Binary Search :

class Solution:
def arrangeCoins(self, n: int) -> int:
left = 1
right = n
while (left <= right):
mid = (left + right) // 2
total =( (mid) * (mid + 1) )/ 2
if total == n:
return mid
if total >n:
right = mid - 1
else:
left = mid + 1
return left - 1

new comers hands up 🙌

I will be posting python question's daily beside leetcode question

69. Sqrt(x) #binary_search #Easy #leet_code_Q9

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.


Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned

dont use built-in function 😅