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 😅

👋 Hey Everyone, here's the solution to yesterday's question.

69. Sqrt(x)

Overview
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.

Approach: Binary Search
Intuition
To find the integer square root of a number x efficiently, we can use the binary search algorithm. The idea is to narrow down the range [0, x] by comparing the mid-point's square with x. This helps us zero in on the integer part of the square root without having to check every number.

Binary search is efficient because it repeatedly divides the search interval in half, making it a logarithmic time complexity algorithm.

Algorithm
1. If x is less than 2, return x because the square root of 0 is 0, and the square root of 1 is 1.
2. Initialize two pointers, left and right, to 2 and x // 2, respectively. We start from 2 because any number less than 2 is already handled by the first step.
3. Perform a binary search:
- Calculate the mid-point: mid = (left + right) // 2.
- Compute the square of mid.
- If mid^2 is greater than x, adjust the right pointer to mid - 1 to search the left half.
- If mid^2 is less than or equal to x, adjust the left pointer to mid + 1 to search the right half. Also, update the variable ans to mid because mid might be the answer.
4. When the loop ends, ans will hold the largest integer whose square is less than or equal to x.
5. Return ans.

Here is the Python implementation of the above approach:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        left, right = 2, x // 2
        ans = 0
        
        while left <= right:
            mid = (left + right) // 2
            num = mid * mid
            
            if num > x:
                right = mid - 1
            else:
                ans = mid
                left = mid + 1
        
        return ans

### Complexity Analysis
Time complexity: O(log x)
- This is due to the binary search algorithm, which cuts the search space in half with each iteration.

Space complexity: O(1)
- We are using a constant amount of space regardless of the input size. Only a few integer variables are used.

This solution efficiently finds the square root of a non-negative integer x rounded down to the nearest integer using binary search.