Ryansblog

1. Brute force approach:   In this process, we use a for loop and iterate the whole 1 to n number. Then, we find out all the divisors by one by one. It is not a optimal solution for this problem. Because, it will take O(n) time to find out all divisors. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i<=n; i++)     {         if(n%2==0) cout<<i<<" ";     }     cout<<endl;     return 0; } Time complexity: O(n) 2. SQRT approach:   In this process, we only iterate in the loop by half of the numbers. Because, if we see we don't need to go through whole n numbers. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i * i<=n; i++)     {         if(n%2==0) cout<<i<<" "<<n/i<<endl;     }     return 0; } Time Complexity: O(sqrt(n))       

  A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very popu

1. Find the first and last position of a element in sorted array:   In this problem, they will gave us a sorted array and a number. We have to find out the first and last position of that element. if the target is not found, we have to return [-1,-1]. We have to solve this problem in O(log_n) time. So, we have to use binary search algorithm. Input:      nums =  [5 ,7 ,7, 8, 9, 10], target=7 Output:   [1, 2] Solution: class Solution { public:     vector < int > searchRange ( vector < int > & nums , int target ) {         int st= 0 ,en= nums . size ()- 1 ;         int index1=- 1 ,index2=- 1 ;         while (st<=en){             int mid = st + (en-st)/ 2 ;             if ( nums [mid]>target) en = mid- 1 ;             else if ( nums [mid]<target) st = mid+ 1 ;             else if ( nums [mid]==target){                 index1 = mid;                 en = mid- 1 ;             }         }         int st1= 0 ,en1= nums . size ()- 1 ;         while (st1<=en1

Lower bound: In binary search, the lower bound is the lowest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element before which the value could be inserted.  STL: int lower = lower_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system. Upper bound: In binary search, the upper bound is the highest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element after which the value could be inserted.  STL: int upper = upper_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system.

Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹.  Here's how it works: 1. Compare x with the middle element. 2. If x matches with the middle element, we return the mid index. 3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half. 4. Else (x is smaller) recur for the left half. This process continues until the element is found or the subarray is empty. Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n) time which is very long time. So, if an array is sorted we always use Binary search. Algorithm: int main() {     optimize();     int arr[]= {1,4,5,8,10,26};     int n = sizeo

Here we have given some important two pointer problems below: 1. Valid Palindrome: A phrase is a  palindrome  if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string  s , return  true  if it is a  palindrome , or  false  otherwise .  -> Solution: class Solution { public:     bool isPalindrome(string s) {       int low=0;       int high=s.length()-1;       while(low<high){           while(!iswalnum(s[low]) && low<high){               low++;           }           while(!iswalnum(s[high]) && low<high){               high--;           }           if(tolower(s[low])!=tolower(s[high])){            return false;           }           low++;           high--;       }         return true;     } }; Time complexity: O(n) Problem link: Valid Palindrome - LeetCode 2. Two Sum II: Given a 1-indexed array of int