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.

153. Find Minimum in Rotated Sorted Array
#leet_code_Q10 #Medium #binary_search #Q_153
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.



Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Don't try to answer at first glance. it's more challenging than it seems

based on this poll we will start doing two pointer and sliding window respectively

344. Reverse String
#Topics #twopointers #strings

Write a function that reverses a string. The input string is given as an array of characters s
You must do this by modifying the input array in-place with O(1) extra memory
Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

link

#leet_code_Q_12 #easy #two_pointer #Q_202 202.Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.



Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:

Input: n = 2
Output: false


Constraints:

1 <= n <= 231 - 1

አዳያመልጣችሁ አሪፍ ዕድል ነው

Answer:

How do you convert a tuple into a list in Python?
a) tuple.toList()
b) list(tuple)
c) tuple.list()