Searching & Sorting.txt

Solutions of these questions are either on GFG or LEETCODE 

---------------------------------------Searching & Sorting-----------------------------------------
1. First and last occurences
used binary search->
public static long FirstOcc(long[]arr,int x){
       		int l = 0;
		int r = arr.length - 1;
		int idx = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (arr[mid] == x) {
				idx = mid;
				r = mid - 1;    //here writer l=mid+1 for last occurence.
			} else if (arr[mid] > x) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return idx;
             }

------------------------------------------------------------------------------------------------------
2. Search in sorted and rotated array O(logn)
 
public int search(int[] arr, int target) {
        
	    int l = 0;
		int r = arr.length - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (arr[mid] == target) {
				return mid;
			}
			// left part sorted
			if (arr[mid] >= arr[l]) {
				// key lies in left part
				if (target <= arr[mid] && target >= arr[l]) {
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			} else { // right part sorted
				if (target >= arr[mid] && target <= arr[r]) {
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
		}
		return -1;
    }

-> in case of duplicates elements

 public boolean search(int[] arr, int target) {
        int l = 0;
		int r = arr.length - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (arr[mid] == target) {
				return true;
			}
			// left part sorted
			if (arr[mid] > arr[l]) {
				// key lies in left part
				if (target < arr[mid] && target >= arr[l]) {
					r = mid;
				} else {
					l = mid + 1;
				}
			} else if(arr[mid]<arr[l]) {// right part sorted
				if (target > arr[mid] && target <= arr[r]) {
					l = mid;
				} else {
					r = mid-1;
				}
			}else{
		                l++;   // cannot use l=mid+1 {for this case->([1,0,1,1,1],0)}
// have no idea about the array, but we can exclude nums[l] because nums[l] == nums[mid]
            		    }
		}
		return false;
    }
------------------------------------------------------------------------------------------------------
3. Minimum Difference Between Largest and Smallest Value in Three Moves->https://youtu.be/Ht6hc3UsvY0
->Suppose if we have been given 1 move then the change/move we do is make largest second largest or make smallest 2nd smallest. and kinda same thing for 3 moves. 
  public int minDifference(int[] nums) {
        if(nums.length<=3)return 0;
        
        Arrays.sort(nums);
        //l-> largest value,s-> smallest value 
        //there will be 4 cases 3l+0s,2l+1s,1l+2s,0l+3s
        //for eg we change the largest value to second largest this will count as a change.
        
        int res=Integer.MAX_VALUE;
        for(int i=0;i<4;i++){
            res=Math.min(res,nums[nums.length-1-3+i]-nums[i]);
        }
        return res;
    }

------------------------------------------------------------------------------------------------------
4. Find missing and repeating
public static int[] findTwoElement(int arr[], int n) {
		int mis = 0;
		int rep = 0;
		for (int i = 0; i < n; i++) {
			if (arr[Math.abs(arr[i]) - 1] >= 0) {
				arr[Math.abs(arr[i]) - 1] *= -1;
			} else {
				rep = Math.abs(arr[i]);
			}
		}
		for (int i = 0; i < n; i++) {
			if (arr[i] > 0) {
				mis = i + 1;
				break;
			}
		}
		int[] res = new int[2];
		res[0] = rep;
		res[1] = mis;
		return res;
	}
------------------------------------------------------------------------------------------------------
5. Majority element (freq more than size/2)
// refer tetris game (question -> freq more than n/2)
//Moore's voting algorithm
    public static int majorityElement(int[] nums) {
		int size = nums.length;
		// finding candidate key for majority.
		int maj_idx = 0;
		int count = 1;
		for (int i = 1; i < size; i++) {
			if (nums[i] == nums[maj_idx]) {
				count++;
			} else {
				count--;
			}
			if (count == 0) {
				maj_idx = i;
				count = 1;
			}
		}
		int cand = nums[maj_idx];
		// checking if it occurs more than n/2 times;
		int c = 0;
		for (int i = 0; i < size; i++) {
			if (nums[i] == cand) {
				c++;
			}
		}
		if (c > size / 2)
			return cand;
		else
			return -1;

	}
------------------------------------------------------------------------------------------------------
6. Majority element II (freq more than n/3)
//here also Moore voting algo is used.
public List<Integer> majorityElement(int[] nums) {
        int num1=-1,num2=-1,count1=0,count2=0;
        for(int i=0;i<nums.length;i++){
            if(num1==nums[i])count1++;
            else if(num2==nums[i])count2++;
            else if(count1==0){num1=nums[i];count1=1;}
            else if(count2==0){num2=nums[i];count2=1;}
            else{
                count1--;count2--;
            }
        }
        count1=0;count2=0;
        for(int i=0;i<nums.length;i++){
            if(num1==nums[i])count1++;
            else if(num2==nums[i])count2++;
        }
        int n=nums.length;
        List<Integer>list=new ArrayList<>();
        if(count1>n/3)list.add(num1);
        if(count2>n/3)list.add(num2);
        return list;
    }
------------------------------------------------------------------------------------------------------
7. Searching in an array where adjacent differ by at most k
 static int search(int arr[], int n, 
                            int x, int k)
    {
        // Traverse the given array starting
        // from leftmost element
        int i = 0;
        while (i < n) {
              
            // If x is found at index i
            if (arr[i] == x)
                return i;
  
            // Jump the difference between 
            // current array element and x
            // divided by k We use max here
            // to make sure that i moves 
            // at-least one step ahead.
            i = i + Math.max(1, Math.abs(arr[i]- x) / k);
        }
------------------------------------------------------------------------------------------------------
8. Find Pair Given Difference
 public  boolean findPair(int arr[], int size, int diff) {
	Arrays.sort(arr);
		int l = 0;
		int r = 1;
		while (l < size && r < size) {
			if (arr[r] - arr[l] == diff && l != r) {
				return true;
			} else if (arr[r] - arr[l] < diff)
				r++;
			else
				l++;
		}
		return false;

	}
------------------------------------------------------------------------------------------------------
9. 4 Sum -Unique Quadruple that sums up to given target ->O(n^3)
public List<List<Integer>> fourSum(int[] arr, int target) {
        List<List<Integer>> ans = new ArrayList<>();
         if(arr==null||arr.length==0)return ans;
		int n = arr.length;
		Arrays.sort(arr);
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				int target1=target-arr[i]-arr[j];
				int l = j + 1;
				int r = n - 1;
				
				while (l < r) {
                    List<Integer> quad = new ArrayList<>();
				    int two_sum=arr[l]+arr[r];
					if (two_sum == target1) {
						quad.add(arr[i]);
						quad.add(arr[j]);
						quad.add(arr[l]);
						quad.add(arr[r]);
					    ans.add(quad);
					  //duplicate skipping process
					  while(l<r && arr[l]==quad.get(2)) l++;
					  while(r>l &&arr[r]==quad.get(3)) r--; 
					} else if (two_sum<target1) {
						l++;
					} else
						r--;
				}
				while(j+1<n && arr[j+1]==arr[j])j++;
			}
				while(i+1<n && arr[i+1]==arr[i])i++;
		}
		return ans; 
    }

4-SumII (LeetCode 454)
-> 
 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer>map = new HashMap<>();
        
        
        for(int a3:nums3){
            for(int a4:nums4){
                map.put(a3+a4,map.getOrDefault(a3+a4,0)+1);
            }
        }
        
        int ans = 0;
        
        for(int a1:nums1){
            for(int a2:nums2){
                int tar = a1+a2;
                ans+= map.getOrDefault(-(a1+a2),0);                
            }
        }
        return ans;
    }

------------------------------------------------------------------------------------------------------
10. Leetcode(198. House Robber) {Maximum sum such that no 2 elements are adjacent}
public int rob(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        if(nums.length==2){
            return Math.max(nums[0],nums[1]);
        }
        
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<dp.length;i++){
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[dp.length-1];
    }
-> S(1)
public int rob(int[] nums) {
        int inc = nums[0];
        int ex = 0;
        
        for(int i=1;i<nums.length;i++){
            int ninc = ex + nums[i];
            int nex = Math.max(inc,ex);
            inc = ninc;
            ex = nex;
        }
        int ans = Math.max(inc,ex);
        return ans;
    }
------------------------------------------------------------------------------------------------------
11. Count triplets with sum smaller than x 
long countTriplets(long arr[], int n,int sum)
    {
        long count=0;
        Arrays.sort(arr);
        for(int i=0;i<n;i++){
            long t1=sum-arr[i];
            int l=i+1;
            int r=n-1;
            while(l<r){
                long tsum=arr[l]+arr[r];
                if(tsum>=t1){
                    r--;
                }else{
                    count+=r-l;
                    l++;
                }
            }
        }
        return count;
    }
------------------------------------------------------------------------------------------------------
12. Zero Sum Subarrays 
public static long find0SumSubarray(long[] arr ,int n) 
    {
        HashMap<Long,Integer>map=new HashMap<>();
        long sum=0;
        long count=0;
        map.put(sum,1);
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            if(map.containsKey(sum)){
                count+=map.get(sum);
                map.put(sum,map.get(sum)+1);
            }else{
                map.put(sum,1);
            }
        }
        return count;
       
    }
------------------------------------------------------------------------------------------------------
13. Product of array except self (for O(n) with S(1)->https://www.youtube.com/watch?v=gREVHiZjXeQ)
-> For O(1) space take a variable product(this will store the righ prefix product), and also we have a output array which doesn't count for extra space, fill the output array with prefix product.
nums->       1   2   3   4		product=1->1*4->4*3->4*3*2
out - >      1   2   6   24                              out[i]=out[i-1]*product;
->                 24   12  8    6
    public int[] productExceptSelf(int[] arr) {
        int n=arr.length;
        int[]l=new int[n];
        int[]r=new int[n];
        int[]res=new int[n];
        l[0]=arr[0];
        r[n-1]=arr[n-1];
        for(int i=1;i<n;i++){
            l[i]=l[i-1]*arr[i];
        }
        for(int j=n-2;j>=0;j--){
            r[j]=r[j+1]*arr[j];
        }
        for(int i=0;i<n;i++){
            if(i==0){
                res[i]=r[i+1];
            }else if(i==n-1){
                res[i]=l[i-1];
            }else{
                res[i]=l[i-1]*r[i+1];
            }
        }
        return res;
    }

------------------------------------------------------------------------------------------------------
14. Minimum Swaps to Sort
Logic->
1. we first make a ArrayList of Pair and put ele along with its index, after that we sort the list.
2. Intuition is after sorting we try to convert the list in previous form with the help of swapping , because after sorting we know that the element that has an index -> the index denotes the position where it should be to convert the list back to previous.
 *Before sorting->{(10,0), (19,1), (6,2), (3,3), (5,4)}
 *After sorting-> {(3,3),(5,4),(6,2),(10,0),(19,1)}
3. we traverse the list and check whether i=idx{idx=pos of ele in prev state}if so continue, if not then swap a[i]with a[ar[i].sec]
 public int minSwaps(int nums[])
    {
        ArrayList<Pair>list = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            Pair p= new Pair(nums[i],i);
            list.add(p);
        }
        
        Collections.sort(list,new Comparator<Pair>(){
            public int compare(Pair p1,Pair p2){
                return p1.ele-p2.ele;
            }
        });
        
        int ans=0;
        for(int i=0;i<nums.length;i++){
            int ix=list.get(i).idx;
            if(i==ix){
        
            }else{
                ans++;
                Pair p1=list.get(i);
                Pair p2=list.get(ix);
                int t1=p1.ele;
                p1.ele=p2.ele;
                p2.ele=t1;
                int t2=p1.idx;
                p1.idx=p2.idx;
                p2.idx=t2;
                i--;
            }
        }
        return ans;
        
    }
    public class Pair{
      int ele=0;
      int idx=0;
      Pair(int x,int y){
          ele=x;
          idx=y;
      }
    }
------------------------------------------------------------------------------------------------------
15. Bishup & Soldiers
public static void BishuNSoldier() {
		int n = scn.nextInt();
		int[] powofS = new int[n];
		int[] preSum = new int[n];
		for (int i = 0; i < n; i++) {
			powofS[i] = scn.nextInt();
		}
		Arrays.sort(powofS);
		preSum[0] = powofS[0];
		for (int i = 1; i < n; i++) {
			preSum[i] = preSum[i - 1] + powofS[i];
		}
		int q = scn.nextInt();

		while (q-- > 0) {
			int p = scn.nextInt();
			int idx = -1;
			int l = 0, r = n - 1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (p >= powofS[mid]) {  // i think it should be preSum[mid] instead of powofS[mid]
					l = mid + 1; // -a
				} else {
					idx = mid; // -b
					r = mid - 1;
				}
			}
			// here it means that idx never went to region b ans move to the end
			if (idx == -1) {
				System.out.println(n + " " + preSum[n - 1]);
			} else {
				System.out.println(idx + " " + preSum[idx-1]);
			}
		}
	}
------------------------------------------------------------------------------------------------------
16. Find Pivot Element in a rotated and sorted array
public static void PivotElementInRotatedAndSortedArray() {
		int[] arr = { 6, 7, 8, 9, 1, 2, 3, 4, 5 };
		int s = 0;
		int e = arr.length - 1;
		while (s <= e) {
			int mid = (s + e) / 2;

			if (mid > s && arr[mid] < arr[mid - 1]) {
				System.out.println(mid - 1);
				break;
			}

			if (mid < e && arr[mid] > arr[mid + 1]) {
				System.out.println(mid);
				break;
			}

			// because the (highest element)pivot element would be present in unsorted area
			if (arr[mid] >= arr[s]) {
				s = mid + 1;
			} else {
				e = mid - 1;
			}
		}
		if (s > e) {
			System.out.println("pivot element doesn't exist");
		}
	}

#) Min in Rotated & Sorted Arrays (unique elements)(LC-153)
 public int findMin(int[] arr) {
        
        if(arr.length==1)return arr[0];
        
        if(arr.length==2)return Math.min(arr[0],arr[1]);
        
        int s = 0;
		int e = arr.length - 1;
		while (s < e) {
			int mid = (s + e) / 2;
            
			if (mid > s && arr[mid] < arr[mid - 1]) {
				return arr[mid];
			}

			if (mid < e && arr[mid] > arr[mid + 1]) {
				return arr[mid+1];
			}

			if (arr[mid] > arr[s] && arr[mid]>arr[e]) {
				s = mid + 1;
			} else {
				e = mid-1;
			}
		}
        return arr[s];
    }
#) Min in Rotated & Sorted Arrays (having duplicates)(LC-154)

 public int findMin(int[] arr) {
        if(arr.length==1)return arr[0];
         
        int s = 0;
		int e = arr.length - 1;
		while (s <= e) {
			int mid = (s + e) / 2;
            
			if(arr[mid]<arr[e]){
                e=mid;
            }else if(arr[mid]>arr[e]){
                s=mid+1;
            }else{
                e--;
            }
		}
        return arr[s];
    }
------------------------------------------------------------------------------------------------------
17. Aggresive cows ->Binary search
public static void AggresiveCows() {

		int nos = scn.nextInt();
		int noc = scn.nextInt();
		int[] ios = new int[nos];
		for (int i = 0; i < ios.length; i++) {
			ios[i] = scn.nextInt();
		}

		Arrays.sort(ios);
		int finalans = 0;
		int lo = 0;
		int hi = ios[nos - 1] - ios[0];

		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			if (isitpossible(ios, noc, mid)) {
				lo = mid + 1;
				finalans = mid;
			} else {
				hi = mid - 1;
			}
		}
		System.out.println(finalans);
	}
	private static boolean isitpossible(int[] ios, int cows, int mid) {
		int cowsplaced = 1;
		int pos = ios[0];
		for (int i = 1; i < ios.length; i++) {
			if (ios[i] - pos >= mid) {
				cowsplaced++;
				pos = ios[i];
			}
			if (cowsplaced == cows) {
				return true;
			}
		}
		return false;
	}
------------------------------------------------------------------------------------------------------
18. Book allocation /Painter's Partition -> Binary search
	public static void BookAllocationProblem() {
		int t = scn.nextInt();
		while (t-- > 0) {
			int nob = scn.nextInt();
			int nos = scn.nextInt();
			int[] nop = new int[nob];

			for (int i = 0; i < nop.length; i++) {
				nop[i] = scn.nextInt();
			}

			int finalans = 0;
			int lo = 0;
			int hi = 0;

			for (int val : nop) {
				hi += val;
			}
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (isitsafe(nop, mid, nos)) {
					finalans = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			System.out.println(finalans);
		}
	}
	private static boolean isitsafe(int[] nop, int mid, int students) {
		int st = 1;
		int pagesread = 0;
		int i = 0;
		while (i < nop.length) {
			if (pagesread + nop[i] <= mid) {
				pagesread += nop[i];
				i++;
			} else {
				pagesread = 0;
				st++;
			}
			if (st > students) {
				return false;
			}
		}
		return true;
	}
------------------------------------------------------------------------------------------------------
19. Kth smallest element again (hackerearth)-> yet to be optimised using binary search
public static void KthSmallestNumAgain() {
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt();
			int q = scn.nextInt();
			ArrayList<pair> vec = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				long x = scn.nextLong();
				long y = scn.nextLong();
				vec.add(new pair(x, y));
			}
			ArrayList<pair> list = MergeIntervals(vec, n);
			while (q-- > 0) {
				long k = scn.nextInt();
				long ans = -1;
				for (int i = 0; i < list.size(); i++) {
					if (list.get(i).second - list.get(i).first + 1 >= k) {
						ans = list.get(i).first + k - 1;
						break;
					} else {
						k = k - (list.get(i).second - list.get(i).first + 1);
					}
				}
				System.out.println(ans);
			}
		}
	}

------------------------------------------------------------------------------------------------------
20.  Kth element in 2 sorted Arrays  (Same as Median of two sorted arrays)
->O(log(min(n,m)))
public long kthElement( int arr1[], int arr2[], int n, int m, int k) {
        if(n > m) {
            return kthElement(arr2, arr1, m, n, k); 
        }
        //as k can be larger than m(larger size array) so in this case if low become 0 than we won't be able to cover all       // elements. so in this case low=1 so that total k elements can be there.
        int low = Math.max(0,k-m), high = Math.min(k,n);
        
        while(low <= high) {
            int cut1 = (low + high) >> 1; 
            int cut2 = k - cut1; 
            int l1 = cut1 == 0 ? Integer.MIN_VALUE : arr1[cut1 - 1]; 
            int l2 = cut2 == 0 ? Integer.MIN_VALUE : arr2[cut2 - 1];
            int r1 = cut1 == n ? Integer.MAX_VALUE : arr1[cut1]; 
            int r2 = cut2 == m ? Integer.MAX_VALUE : arr2[cut2]; 
            
            if(l1 <= r2 && l2 <= r1) {
                return Math.max(l1, l2);
            }
            else if (l1 > r2) {
                high = cut1 - 1;
            }
            else {
                low = cut1 + 1; 
            }
        }
        return 1; 
    }
------------------------------------------------------------------------------------------------------
21. Smallest factorial number
-> logic
->Trailing 0s in n! = Count of 5s in prime factors of n!
                  = floor(n/5) + floor(n/25) + floor(n/125) + .... 
here 2 and 5 both makes 10 hence help in finding trailing zeros so we generally find no. of 2s and 5s and take min(2s,5s), but 5s are always in less number so we only find no. of 5s
Time-(logn*logm);
public static int findNum(int noz) {
		int lo = 1;
		int hi = noz * 5; // max no which have this much trailing zero in its factorial
		int ans=-1;
		while(lo<=hi) {
			int mid=(lo+hi)/2;
			if(Findzeros(mid)>=noz) {
				ans=mid;
				hi=mid-1;
			}else if(Findzeros(mid)<noz) {
				lo=mid+1;
			}
		}
		return ans;
	}
	public static int Findzeros(int n) {
		int count = 0;
		for (int i = 5; n / i >= 1; i *= 5) {
			count += n / i;
		}
		return count;
	}
------------------------------------------------------------------------------------------------------
22. Find the missing number in Arithmetic Progression->logn
public static int findMissingterm(int[] arr, int n) {
		int diff = (arr[n - 1] - arr[0]) / n;
		return findmissing(arr, diff, 0, n - 1, n);
	}

	private static int findmissing(int[] arr, int diff, int l, int r, int n) {
		if (l >= r) {
			return Integer.MAX_VALUE;
		}
		int mid = l + (r - l) / 2;
		if (mid < n && arr[mid + 1] - arr[mid] != diff) {
			return arr[mid] + diff;
		}
		if (mid > 0 && arr[mid] - arr[mid - 1] != diff) {
			return arr[mid - 1] + diff;
		}
		// If the elements till mid follow AP
		if (arr[mid] == arr[0] + mid * diff) {
			return findmissing(arr, diff, mid + 1, r, n);
		}
		return findmissing(arr, diff, l, mid - 1, n);

	}

------------------------------------------------------------------------------------------------------
23. Job sequencing problem
Intuition-> start performing job as late as possible (under deadline obviously),in this case you can have the advantage of performing jobs which may give high profits but have less deadline.
//Greedy Approach
    public int[] JobScheduling(Job arr[], int n)
    {
       Arrays.sort(arr,(a,b)->(b.profit-a.profit));
       int max_deadline=0;
       for(int i=0;i<n;i++){
           if(arr[i].deadline>max_deadline){
               max_deadline=arr[i].deadline;
           }
       }
       int[] result=new int[max_deadline+1];
       for(int i=1;i<=max_deadline;i++){
           result[i]=-1;
       }
       int count_jobs=0,job_profit=0;
       //traverse through (i==job_id);
       for(int i=0;i<n;i++){
           for(int j=arr[i].deadline;j>0;j--){
               if(result[j]==-1){
                 result[j]=i;   
                 count_jobs++;
                 job_profit+=arr[i].profit;
                 break;
               }
           }
       }
       int[]res=new int[2];
       res[0]=count_jobs;
       res[1]=job_profit;
       return res;
    }
------------------------------------------------------------------------------------------------------
24. EKO-Eko -> binary search
public static void EkoSpoj() {
		int n=scn.nextInt();
		long M=scn.nextInt();
		int[]arr= new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=scn.nextInt();
		}
		Arrays.sort(arr);
		long ans=0;
		long lo=0;
		long hi=arr[n-1];
		while(lo<=hi) {  //Here search space is heights of trees
			long mid=lo+(hi-lo)/2;  //to avoid overflow here
			long woods=0;
			for(int i=0;i<n;i++) {
				if(mid<arr[i])
				woods+=Math.abs(mid-arr[i]);
			}
			if(woods>=M) {
				lo=mid+1;
				ans=mid;
			}else {
				hi=mid-1;
			}
		}
		System.out.println(ans);
	}
------------------------------------------------------------------------------------------------------
25. Roti Prata -> binary search
public static void PrataSpoj() {
		int t = scn.nextInt();
		while (t-- > 0) {
			int prat = scn.nextInt();
			int cooks = scn.nextInt();
			int[] rank = new int[cooks];
			for (int i = 0; i < cooks; i++) {
				rank[i] = scn.nextInt();
			}
			int lo = 0;
			int hi = Integer.MAX_VALUE;
			int ans = 0;
			while (lo <= hi) {
				int mid = lo + (hi - lo) / 2;
				if (isItPossible(rank, mid, prat)) {
					hi = mid - 1;
					ans = mid;
				} else {
					lo = mid + 1;
				}
			}
			System.out.println(ans);
		}
	}
	private static boolean isItPossible(int[] rank, int tl, int prat) {
		int p = 0;
		int time = 0;
		for (int i = 0; i < rank.length; i++) {
			int j = 2;
			time = rank[i];
			while (time <= tl) {
				p++;
				time += (rank[i] * j);
				j++;
			}
			if (p >= prat) {
				return true;
			}
		}
		return false;
	}
------------------------------------------------------------------------------------------------------
26. The DoubleHelix /MaximumSumPathIn2Arrays->2 pointer
public static void TheDoubleHeLiX() {
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt();
			int[] arr = new int[n];
			for (int k = 0; k < n; k++) {
				arr[k] = scn.nextInt();
			}

			int m = scn.nextInt();
			int[] brr = new int[m];
			for (int l = 0; l < m; l++) {
				brr[l] = scn.nextInt();
			}
			
			int i = 0, j = 0;
			long suma = 0;
			long sumb = 0;
			long ans_sum = 0;
			while (i < n && j < m) {
				if (arr[i] > brr[j]) {
					sumb += brr[j];
					j++;
				} else if (arr[i] < brr[j]) {
					suma += arr[i];
					i++;
				} else {
					ans_sum += arr[i] + Math.max(suma, sumb);
					suma = 0;
					sumb = 0;
					i++;
					j++;
				}
			}
			// if some sum is remaining
			if (i == n) {
				while (j < m) {
					sumb += brr[j++];
				}
			}
			if (j == m) {
				while (i < n) {
					suma += arr[i++];
				}
			}
			ans_sum += Math.max(suma, sumb);
			System.out.println(ans_sum);
		}
------------------------------------------------------------------------------------------------------
27. Subset Sums Spoj (Used Meet in middle approach +binary search)
------------------------------------------------------------------------------------------------------
28. Single Element In Sorted Array | Leetcode-540 -BinarySearch
Intuition->Here we take low at 0 index and high at length-1th index(why?,ans later),now we have to find the break point where the element is present, through observations we found that in->
 Left half-> { Even index->1st instance ,odd index-> 2nd instance}
 Right half->{ Odd index->1st instance, even index-> 2nd instance }
-> we find the mid element then check whether it is in the left half or in right half, if in left half then shrink left half by low=mid+1; or if it is in right half then shrink right half by high=mid-1, when we find the BREAK POINT, we (low) would have passed the high. so the ans is (arr[low]).
{1,1,2,3,3,4,4,8,8} ans =2    {we took high as length-1 for such array where ans is in last of array->{1,1,3,3,4,4,5}}

 public int singleNonDuplicate(int[] nums) {
        int lo=0,hi=nums.length-2;
        
        while(lo<=hi){
            int mid=(lo+hi)>>1;
          if(nums[mid]==nums[mid^1]){   //mid^1 gives next pre-even if mid is odd, else give next odd if mid is even
                lo=mid+1;
            }else{
                hi=mid-1;
            }
        }
        return nums[lo];
    }
-----------------------------------------------------------------------------------------------------
29. Nth Root of a Number (Binary Search) 
->O(nlog(m*10)^d) d=desired decimal place ,(m*10 because there are 10 digits)

private static double multiply(double number, int n) {
        double ans = 1.0;
        for(int i = 1;i<=n;i++) {
            ans = ans * number;
        }
        return ans; 
    }
    private static void getNthRoot(int n, int m) {
        double low = 1;
        double high = m;
        double eps = 1e-6; 
        
        while((high - low) > eps) {
            double mid = (low + high) / 2.0; 
            if(multiply(mid, n) < m) {
                low = mid; 
            }
            else {
                high = mid; 
            }
        }
        
        System.out.println(low + " " + high);  
        
        // just to check
         System.out.println(Math.pow(m, (double)(1.0/(double)n))); 
    }
	public static void main (String[] args) {
		int n = 17, m = 89; 
		getNthRoot(n, m); 
	}

-----------------------------------------------------------------------------------------------------
30. Find the only element in a sorted array of size n
-> log(N)

static int findRepeatingElement(int arr[], int low, int high)
    {
        // low = 0 , high = n-1;
        if (low > high)
            return -1;
      
        int mid = (low + high) / 2;
      
        // Check if the mid element is the repeating one
        if (arr[mid] != mid + 1)
        {
            if (mid > 0 && arr[mid]==arr[mid-1])
                return mid;
      
            // If mid element is not at its position that means
            // the repeated element is in left
            return  findRepeatingElement(arr, low, mid-1);
        }
      
        // If mid is at proper position then repeated one is in
        // right.
        return findRepeatingElement(arr, mid+1, high);
    }
-----------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------