// Binary Search : Time Complexity : O(n * log(sum - mx))   or   O(n * log(sum))

import java.util.*;
import java.io.*;

class GFG { 
    
    public static void main(String args[]) 
    { 
        int arr[]={10,20,10,30};
        int n=arr.length;
        int k=2;
        
    	System.out.print(minPages(arr,n,k));     // OUTPUT : 40 
    } 
    
    public static boolean isFeasible(int arr[],int n,int k, int ans){
        int req=1,sum=0;
        for(int i=0;i<n;i++){
            if(sum+arr[i]>ans){
                req++;
                sum=arr[i];
            }
            else{
                sum+=arr[i];
            }
        }
        return (req<=k);
    }
    
    public static int minPages(int arr[],int n, int k){
        int sum=0,mx=0;
        for(int i=0;i<n;i++){
            sum+=arr[i];
            mx=Math.max(mx,arr[i]);
        }
        int low=mx,high=sum,res=0;
        
        while(low<=high){
            int mid=(low+high)/2;
            if(isFeasible(arr,n,k,mid)){
                res=mid;
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        return res;
    } 
} 







// Naive Method : Time : Exponential (very slow)

import java.util.*;
import java.io.*;

class GFG { 
    
    public static void main(String args[]) 
    { 
        int arr[]={10,20,10,30};
        int n=arr.length;
        int k=2;
        
    	System.out.print(minPages(arr,n,k));     // OUTPUT : 40 
    } 
    
    public static int sum(int arr[],int b, int e){
        int s=0;
        for(int i=b;i<=e;i++)
            s+=arr[i];
        return s;
    }
    
    public static int minPages(int arr[],int n, int k){
        if(k==1)
            return sum(arr,0,n-1);
        if(n==1)
            return arr[0];
        int res=Integer.MAX_VALUE;
        for(int i=1;i<n;i++){
            res=Math.min(res,Math.max(minPages(arr,i,k-1),sum(arr,i,n-1)));
        }
        return res;
    } 
} 

// Method-2 : Time Complexity : O(n),  Auxiliary Space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 

	static int repeat(int arr[], int n)
	{
		int slow = arr[0], fast = arr[0];

		do{
			slow = arr[slow];
			fast = arr[arr[fast]];
		
		}while(slow != fast);
		
		slow = arr[0];

		while(slow != fast)
		{
			slow = arr[slow];
			fast = arr[fast];
		}
		return slow;
	}

	public static void main(String args[]) 
    {
		int arr[] = {1, 3, 2, 4, 6, 5, 7, 3}, n= 8;

        System.out.println(repeat(arr, n));     // OUTPUT : 3
    } 

}






// Method-1 : Time Complexity : O(n),  Auxiliary Space : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int repeat(int arr[], int n)
	{
		boolean visit[] = new boolean[n];

		for(int i = 0; i < n; i++)
		{
			if(visit[arr[i]])
				return arr[i];
			visit[arr[i]] = true;
		}

		return -1;
	}

	public static void main(String args[]) 
    {
		int arr[] = {0, 2, 1, 3, 2, 2}, n= 6;

        System.out.println(repeat(arr, n));     // OUTPUT : 2
    } 

}

import java.util.*;
import java.io.*;


class GFG 
{ 
	static double getMed(int a1[], int a2[], int n1, int n2)
	{
		int begin1 = 0, end1 = n1;

		while(begin1 < end1)
		{
			int i1 = (begin1 + end1) / 2;
			int i2 = ((n1 + n2 + 1) / 2 )- i1;

			int min1 = (i1 == n1)?Integer.MAX_VALUE:a1[i1];
			int max1 = (i1 == 0)?Integer.MIN_VALUE:a1[i1 - 1];
			
			int min2 = (i2 == n2)?Integer.MAX_VALUE:a2[i2];
			int max2 = (i2 == 0)?Integer.MIN_VALUE:a2[i2 - 1];

			if(max1 <= min2 && max2 <= min1)
			{
				if((n1 + n2) % 2 == 0)
					return ((double)Math.max(max1, max2) + Math.min(min1, min2)) / 2;
				else
					return (double) Math.max(max1, max2);
			}
			else if(max1 > min2)
				end1 = i1 - 1;
			else 
				begin1 = i1 + 1;
		}
		
		return -1;
	}

	public static void main(String args[]) 
    {
		int a1[] = {10, 20, 30, 40, 50}, n1 = 5, a2[] = {5, 15, 25, 35, 45}, n2 = 5;
		
        System.out.println(getMed(a1, a2, n1, n2));     // OUTPUT : 27.5
    } 

}

// Java program to find a triplet 
class FindTriplet { 

	// returns true if there is triplet with sum equal 
	// to 'sum' present in A[]. Also, prints the triplet 
	boolean find3Numbers(int A[], int arr_size, int sum) 
	{ 
		int l, r; 

		/* Sort the elements */
		quickSort(A, 0, arr_size - 1); 

		/* Now fix the first element one by one and find the 
		other two elements */
		for (int i = 0; i < arr_size - 2; i++) { 

			// To find the other two elements, start two index variables 
			// from two corners of the array and move them toward each 
			// other 
			l = i + 1; // index of the first element in the remaining elements 
			r = arr_size - 1; // index of the last element 
			while (l < r) { 
				if (A[i] + A[l] + A[r] == sum) { 
					System.out.print("Triplet is " + A[i] + ", " + A[l] + ", " + A[r]); 
					return true; 
				} 
				else if (A[i] + A[l] + A[r] < sum) 
					l++; 

				else // A[i] + A[l] + A[r] > sum 
					r--; 
			} 
		} 

		// If we reach here, then no triplet was found 
		return false; 
	} 

	int partition(int A[], int si, int ei) 
	{ 
		int x = A[ei]; 
		int i = (si - 1); 
		int j; 

		for (j = si; j <= ei - 1; j++) { 
			if (A[j] <= x) { 
				i++; 
				int temp = A[i]; 
				A[i] = A[j]; 
				A[j] = temp; 
			} 
		} 
		int temp = A[i + 1]; 
		A[i + 1] = A[ei]; 
		A[ei] = temp; 
		return (i + 1); 
	} 

	/* Implementation of Quick Sort 
	A[] --> Array to be sorted 
	si --> Starting index 
	ei --> Ending index 
	*/
	void quickSort(int A[], int si, int ei) 
	{ 
		int pi; 

		/* Partitioning index */
		if (si < ei) { 
			pi = partition(A, si, ei); 
			quickSort(A, si, pi - 1); 
			quickSort(A, pi + 1, ei); 
		} 
	} 

	// Driver program to test above functions 
	public static void main(String[] args) 
	{ 
		FindTriplet triplet = new FindTriplet(); 
		int A[] = { 1, 4, 45, 6, 10, 8 }; 
		int sum = 22; 
		int arr_size = A.length; 

		triplet.find3Numbers(A, arr_size, sum);    // OUTPUT : Triplet is 4, 8, 10
	} 
} 

import java.util.*;
import java.io.*;

class Solution
{
    static int isPresent(int arr[], int n, int sum)
    {
        int l = 0, h = n-1;
        
        while(l <= h)
        {
            if(arr[l] + arr[h] == sum)
              return 1;
            else if(arr[l] + arr[h] > sum)
                h--;
            else l++;
        }
        
        return 0;
    }
    
    public static void main (String[] args) 
    {
        int arr[] = new int[]{2, 3, 7, 8, 11};
        int n = arr.length;
        int sum = 14;
        
        System.out.println(isPresent(arr, n, sum));    // OUTPUT : 1
    }
}

// Java implementation using Hashing 
import java.io.*; 
import java.util.HashSet; 

class PairSum { 
    
	static void printpairs(int arr[], int sum) 
	{ 
		HashSet<Integer> s = new HashSet<Integer>(); 
		for (int i = 0; i < arr.length; ++i) { 
			int temp = sum - arr[i]; 

			// checking for condition 
			if (s.contains(temp)) { 
				System.out.println("Pair with given sum " + sum + " is (" + arr[i] + ", " + temp + ")"); 
			} 
			s.add(arr[i]); 
		} 
	} 

	// Main to test the above function 
	public static void main(String[] args) 
	{ 
		int A[] = { 1, 4, 45, 6, 10, 8 }; 
		int n = 16; 
		printpairs(A, n); 
	} 
} 


// OUTPUT : Pair with given sum 16 is (10, 6)

// Efficient Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int getPeak(int arr[], int n)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if((mid == 0 || arr[mid - 1] <= arr[mid]) &&
				(mid == n - 1 || arr[mid + 1] <= arr[mid]))
				return mid;
			if(mid > 0 && arr[mid - 1] >= arr[mid])
				high = mid -1;
			else
				low = mid + 1;
		}
		
		return -1;
	}

	public static void main(String args[]) 
    {
		int arr[] = {5, 20, 40, 30, 20, 50, 60}, n = 7;

        System.out.println(getPeak(arr, n));    //   OUTPUT : 20
    } 

}
 
 
 
 
 
// Naive Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int getPeak(int arr[], int n)
	{
		if(n == 1)
			return arr[0];
		if(arr[0] >= arr[1])
			return arr[0];
		if(arr[n - 1] >= arr[n - 2])
			return arr[n - 1];

		for(int i = 1; i < n - 1; i++)
			if(arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
				return arr[i];
				
		return -1;
	}

	public static void main(String args[]) 
    {
		int arr[] = {5, 10, 11, 12, 20, 12}, n = 6;

        System.out.println(getPeak(arr, n));  //   OUTPUT : 2
    } 

}

// Efficient Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 

	static int search(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(arr[mid] == x)
				return mid;
			if(arr[low] < arr[mid])
			{
				if(x >= arr[low] && x < arr[mid])
					high = mid - 1;
				else 
					low = mid + 1;
			}
			else
			{
				if(x > arr[mid] && x <= arr[high])
					low = mid + 1;
				else
					high = mid - 1;
			}
		}
		
		return -1;
	}

	public static void main(String args[]) 
    {

		int arr[] = {10, 20, 40, 60, 5, 8}, n = 6;

		int x = 5;

        System.out.println(search(arr, n, x));      // OUTPUT : 4

    } 

}
 
 
 
 
 
// Naive Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int search(int arr[], int n, int x)
	{
		for(int i = 0; i < n; i++)
			if(arr[i] == x)
				return i;

		return -1;
	}

	public static void main(String args[]) 
    {
		int arr[] = {100, 200, 400, 1000, 10, 20}, n = 6;

		int x = 10;

        System.out.println(search(arr, n, x));      // OUTPUT : 4
    } 

}

// Efficient Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(arr[mid] == x)
			return mid;

		else if(arr[mid] > x)
			return bSearch(arr, low, mid - 1, x);

		else
			return bSearch(arr, mid + 1, high, x);
	}

	static int search(int arr[], int x)
	{
		if(arr[0] == x) return 0;

		int i = 1;

		while(arr[i] < x)
			i = i * 2;

		if(arr[i] == x) return i;

		return bSearch(arr, i / 2 + 1, i - 1, x);
	}

	public static void main(String args[]) 
    {
		int arr[] = {1, 2, 3, 40, 50};

		int x = 4;

        System.out.println(search(arr, x));     // OUTPUT : -1
    } 

}
 
 
 
 
 
// Naive Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int search(int arr[], int x)
	{
		int i = 0;

		while(true)
		{
			if(arr[i] == x) return i;

			if(arr[i] > x) return -1;

			i++;
		}
	}

	public static void main(String args[]) 
    {
		int arr[] = {1, 2, 3, 5, 5};

		int x = 4;

		System.out.println(search(arr, x));     // OUTPUT : -1
    } 

}

// Efficient Code

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int sqRootFloor(int x)
	{
		int low = 1, high = x, ans = -1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			int mSq = mid * mid;

			if(mSq == x)
				return mid;
			else if(mSq > x)
				high = mid - 1;
			else
			{
				low = mid + 1;
				ans = mid;
			}
		}

		return ans;
	}

	public static void main(String args[]) 
    {

		System.out.println(sqRootFloor(10));

    } 

}





// Naive Code

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int sqRootFloor(int x)
	{
		int i = 1;

		while(i * i <= x)
			i++;

		return i - 1;
	}

	public static void main(String args[]) 
    {

		System.out.println(sqRootFloor(15));

    } 

}

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int countOnes(int arr[], int n)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(arr[mid] == 0)
				low = mid + 1;
			else
			{
				if(mid == 0 || arr[mid - 1] == 0)
					return (n - mid);
				else 
					high = mid -1;
			}
		}

		return 0;		
	}

	public static void main(String args[]) 
    {
        int arr[] = {0, 0, 1, 1, 1, 1}, n = 6;

		System.out.println(countOnes(arr, n));   // OUTPUT : 4

    } 

}

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int firstOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == 0 || arr[mid - 1] != arr[mid])
					return mid;

				else
					high = mid - 1;
			}

		}

		return -1;
	}

	static int lastOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == n - 1 || arr[mid + 1] != arr[mid])
					return mid;

				else
					low = mid + 1;
			}

		}

		return -1;
	}
	
	
	static int countOcc(int arr[], int n, int x)
	{
		int first = firstOcc(arr, n, x);

		if(first == -1)
			return 0;
		else 
			return lastOcc(arr, n, x) - first + 1;
	}

	public static void main(String args[]) 
    {
        int arr[] = {10, 20, 20, 20, 40, 40}, n = 6;

		int x = 20;

		System.out.println(countOcc(arr, n, x));   // OUTPUT : 3

    } 
    
}

// Iterative Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int lastOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == n - 1 || arr[mid + 1] != arr[mid])
					return mid;

				else
					low = mid + 1;
			}

		}

		return -1;
	}
	
	public static void main(String args[]) 
	{
	    int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;
	    
	    int x = 10;
	    
	    System.out.println(lastOcc(arr, n, x));   // OUTPUT : 4
    } 
    
}
 
 
 
 
 
 
// Recursive Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int lastOcc(int arr[], int low, int high, int x, int n)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(x > arr[mid])
			return lastOcc(arr, mid + 1, high, x, n);

		else if(x < arr[mid])
			return lastOcc(arr, low, mid - 1, x, n);

		else
		{
			if(mid == n - 1 || arr[mid + 1] != arr[mid])
				return mid;

			else
				return lastOcc(arr, mid + 1, high, x, n);
		}
	}
	
	public static void main(String args[]) 
	{
	    int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;
	    
	    int x = 10;
	    
	    System.out.println(lastOcc(arr, 0, n - 1, x, n));   // OUTPUT : 4
    } 

}

// Efficient Code (Iterative)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int firstOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == 0 || arr[mid - 1] != arr[mid])
					return mid;

				else
					high = mid - 1;
			}

		}
		return -1;
	}

	public static void main(String args[]) 
    {
        int arr[] = {5, 10, 10, 10, 20}, n = 5;

		int x = 10;

        System.out.println(firstOcc(arr, n, x));   // OUTPUT : 1
    } 
}






// Efficient Code (Recursive)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int firstOcc(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(x > arr[mid])
			return firstOcc(arr, mid + 1, high, x);

		else if(x < arr[mid])
			return firstOcc(arr, low, mid - 1, x);

		else
		{
			if(mid == 0 || arr[mid - 1] != arr[mid])
				return mid;

			else
				return firstOcc(arr, low, mid - 1, x);
		}
	}

	public static void main(String args[]) 
    {
        int arr[] = {5, 10, 10, 15, 20, 20, 20}, n = 7;

		int x = 20;
		
		System.out.println(firstOcc(arr, 0, n - 1, x));   // OUTPUT : 4
    } 
}






// Naive Code

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int firstOccurrence(int arr[], int n, int x)
	{
		for(int i = 0; i < n; i++)
			if(arr[i] == x)
				return i;

		return -1;
	}

	public static void main(String args[]) 
    {
        int arr[] = {5, 10, 10, 15, 15}, n = 5;

		int x = 15;
    
        System.out.println(firstOccurrence(arr, n, x));   // OUTPUT : 3
    } 
}