Snippets Collections
// Max Heap:

// Java program to demonstrate working of PriorityQueue in Java
import java.util.*;

class Test{
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pq 
        = new PriorityQueue<Integer>(
            Collections.reverseOrder());

        // Adding items to the pQueue using add()
        pq.add(10);
        pq.add(20);
        pq.add(15);
        
        // Above PriorityQueue is stored as following
        //       20
        //      /  \
        //    10    15

        // Printing the top element of PriorityQueue
        System.out.println(pq.peek());

        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pq.poll());

        // Post poll() PriorityQueue looks like
        //       15
        //      /  
        //    10   

        // Printing the top element again
        System.out.println(pq.peek());
    }
}

// OUTPUT : 
10
10
15










// Min Heap(default)

// Java program to demonstrate working of PriorityQueue in Java
import java.util.*;

class Test{
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // Adding items to the pQueue using add()
        pq.add(10);
        pq.add(20);
        pq.add(15);
        
       
        // Printing the top element of PriorityQueue
        System.out.println(pq.peek());

        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pq.poll());


        // Printing the top element again
        System.out.println(pq.peek());
    }
}

// OUTPUT : 
20
20
15
import java.util.*;
import java.io.*;
  
public class HeapSort 
{ 
	public void buildheap(int arr[], int n){
        for (int i = n / 2 - 1; i >= 0; i--) 
		    heapify(arr, n, i);
    }
	
	public void sort(int arr[]) 
	{ 
		int n = arr.length; 

		buildheap(arr,n); 
 
		for (int i=n-1; i>0; i--) 
		{ 
			 
			int temp = arr[0]; 
			arr[0] = arr[i]; 
			arr[i] = temp; 

			heapify(arr, i, 0); 
		} 
	} 

	void heapify(int arr[], int n, int i) 
	{ 
		int largest = i;  
		int l = 2*i + 1; 
		int r = 2*i + 2; 

		if (l < n && arr[l] > arr[largest]) 
			largest = l; 
 
		if (r < n && arr[r] > arr[largest]) 
			largest = r; 

		if (largest != i) 
		{ 
			int swap = arr[i]; 
			arr[i] = arr[largest]; 
			arr[largest] = swap; 

			heapify(arr, n, largest); 
		} 
	} 

	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i]+" "); 
		System.out.println(); 
	} 
 
	public static void main(String args[]) 
	{ 
		int arr[] = {12, 11, 13, 5, 6, 7}; 
		int n = arr.length; 

		HeapSort ob = new HeapSort(); 
		ob.sort(arr); 

		System.out.println("Sorted array is"); 
		printArray(arr); 
	} 
} 
import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public void buildHeap(){
            for(int i=(size-2)/2;i>=0;i--)
                minHeapify(i);
        }
    
    }
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
    } 
   
} 
import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
               int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public int extractMin() 
        { 
            if (size <= 0) 
                return Integer.MAX_VALUE; 
            if (size == 1) 
            { 
                size--; 
                return arr[0]; 
            }  
            int temp = arr[0]; 
            arr[0] = arr[size-1]; 
            arr[size-1] = temp;
            size--; 
            minHeapify(0); 
          
            return arr[size]; 
        }
    
        void decreaseKey(int i, int x) 
        { 
            arr[i] = x; 
            while (i != 0 && arr[parent(i)] > arr[i]) 
            { 
               int temp = arr[i]; 
               arr[i] = arr[parent(i)]; 
               arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
        void deleteKey(int i) 
        { 
            decreaseKey(i, Integer.MIN_VALUE); 
            extractMin(); 
        }
    
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.deleteKey(0);
        h.insert(15);
        h.insert(20);
        System.out.println(h.extractMin());
        h.decreaseKey(2, 1);
        System.out.println(h.extractMin());
    } 
} 
import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap
    {
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
                i = parent(i); 
            } 
        }
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public int extractMin() 
        { 
            if (size <= 0) 
                return Integer.MAX_VALUE; 
            if (size == 1) 
            { 
                size--; 
                return arr[0]; 
            }  
            int temp = arr[0]; 
            arr[0] = arr[size-1]; 
            arr[size-1] = temp;
            size--; 
            minHeapify(0); 
          
            return arr[size]; 
        } 
        
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.insert(15);
        h.insert(20);
        System.out.print(h.extractMin());     // OUTPUT : 2
    } 
} 
import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
               int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.insert(15);
        h.insert(20);
    } 
   
} 
import java.util.*;
import java.io.*;
  
class Test { 
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
    } 
   
} 
import java.util.*;
import java.io.*;

class Solution
{
    public static void main (String[] args) 
    {
        int a[] = new int[]{10,5,30,15,7};
	    int l=0,r=4;
        
        mergeSort(a,l,r);
    	for(int x: a)
	        System.out.print(x+" ");    // OUTPUT : 5 7 10 15 30 
        
    }
    
    static void merge(int arr[], int l, int m, int h){
    
        int n1=m-l+1, n2=h-m;
        int[] left=new int[n1];
        int[]right=new int[n2];
        
        for(int i=0;i<n1;i++)
            left[i]=arr[i+l];
        for(int j=0;j<n2;j++)
            right[j]=arr[m+1+j];
            
        int i=0,j=0,k=l;
        while(i<n1 && j<n2){
            if(left[i]<=right[j])
                arr[k++]=left[i++];
            else
                arr[k++]=right[j++];
        }
        while(i<n1)
            arr[k++]=left[i++];
        while(j<n2)
            arr[k++]=right[j++];    
    }
    
    static void mergeSort(int arr[],int l,int r){
        if(r>l){
            int m=l+(r-l)/2;
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,r);
            merge(arr,l,m,r);
        }
    }
}
// Efficient Code :

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

class Solution
{
    public static void main (String[] args) 
    {
        int a[] = new int[]{10,15,20,40};
        int b[] = new int[]{5,6,6,10,15};
        
        int m = a.length;
        int n = b.length;
        merge(a,b,m,n);
    }
    
    static void merge(int a[], int b[], int m, int n)
    {
        int i=0,j=0;
        while(i<m && j<n){
            if(a[i]<b[j])
                System.out.print(a[i++]+" ");
            else
                System.out.print(b[j++]+" ");
        }
        while(i<m)
            System.out.print(a[i++]+" ");
        while(j<n)
            System.out.print(b[j++]+" ");    
    }
}








// Naive Code :

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

class Solution
{
    public static void main (String[] args) 
    {
        int a[] = new int[]{10,15,20,40};
        int b[] = new int[]{5,6,6,10,15};
        
        int m = a.length;
        int n = b.length;
        merge(a,b,m,n);
        
    }
    
    static void merge(int a[], int b[], int m, int n){
    
        int[] c=new int[m+n];
        for(int i=0;i<m;i++)
            c[i]=a[i];
        for(int j=0;j<n;j++)
            c[j+m]=b[j];
        
        Arrays.sort(c);
        
        for(int i=0;i<m+n;i++)
            System.out.print(c[i]+" ");
    }
}
import java.util.*;
import java.io.*;

class Solution
{
    public static void main (String[] args) 
    {
        int arr[] = new int[]{50,20,40,60,10,30};
        
        int n = arr.length;
        iSort(arr,n);
        
        for(int x:arr)
            System.out.print(x+" ");    // OUTPUT : 10 20 30 40 50 60 
        
    }
    
    static void iSort(int arr[],int n)
    {
        for(int i=1;i<n;i++){
            int key = arr[i];
            int j=i-1;
            while(j>=0 && arr[j]>key){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=key;
        }
    }
}
import java.io.*;

class GFG {
    
    static void selectionSort(int arr[], int n){
        for(int i = 0; i < n; i++){
            int min_ind = i;
            
            for(int j = i + 1; j < n; j++){
                if(arr[j] < arr[min_ind]){
                    min_ind = j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[min_ind];
            arr[min_ind] = temp;
        }
    }
    
	public static void main (String[] args) {
	    int a[] = {2, 1, 4, 3};
	    selectionSort(a, 4);
	    
	    for(int i = 0; i < 4; i++){
	        System.out.print(a[i] + " ");    // OUTPUT : 1 2 3 4
	    }
	}
}
// Optimised Bubble Sort

import java.io.*;

class GFG {
    
    static void bubbleSort(int arr[], int n){
        boolean swapped;
        
        for(int i = 0; i < n; i++){
            
            swapped = false;
            
            for(int j = 0; j < n - i - 1; j++){
                if( arr[j] > arr[j + 1]){
                    
                    // swapping
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    
                    swapped = true;
                    
                }
            }
            if(swapped == false)
            break;
        }
    }
    
	public static void main (String[] args) {
	    int a[] = {2, 1, 4, 3};
	    bubbleSort(a, 4);
	    
	    for(int i = 0; i < 4; i++){
	        System.out.print(a[i] + " ");     // OUTPUT : 1 2 3 4
	    }
	}
}






// Bubble Sort

import java.io.*;

class GFG {
    
    static void bubbleSort(int arr[], int n){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n - i - 1; j++){
                if( arr[j] > arr[j + 1]){
                    
                    // swapping
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    
                }
            }
        }
    }
    
	public static void main (String[] args) {
	    int a[] = {2, 1, 4, 3};
	    bubbleSort(a, 4);
	    
	    for(int i = 0; i < 4; i++){
	        System.out.print(a[i] + " ");     // OUTPUT : 1 2 3 4
	    }
	}
}
// 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
    } 
}
// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

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

class GFG 
{ 
	static int bSearch(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;

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

			else
				low = mid + 1;
		}

		return -1;
	}

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

		int x = 25;
    
        System.out.println(bSearch(arr, n, x));  // Output : -1
		
    } 

}





// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

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);
	}

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

		int x = 20;

        System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
    } 
}
// Efficient Code O(n) : 

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static int longestDistinct(String str) 
    { 
    	int n = str.length(); 
    	int res = 0;
    	int prev[]=new int[256];
    	Arrays.fill(prev,-1);
    	int i=0;
    	for (int j = 0; j < n; j++)
    	{
    	    i=Math.max(i,prev[str.charAt(j)]+1);
    	    int maxEnd=j-i+1;
    	    res=Math.max(res,maxEnd);
    	    prev[str.charAt(j)]=j;
    	} 
    	return res; 
    } 
    
    public static void main(String args[]) 
    { 
        String str = "geeksforgeeks"; 
	    int len = longestDistinct(str);  // OUTPUT : 7
        System.out.print("The length of longest distinct characters substring is "+ len); 
    } 
} 






// Better Approach O(n2) :

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static int longestDistinct(String str) 
    { 
    	int n = str.length(); 
    	int res = 0;
    	for (int i = 0; i < n; i++){
    	    boolean visited[]=new boolean[256];
    	    for(int j=i;j<n;j++){
    	        if(visited[str.charAt(j)]==true){
    	            break;
    	        }
    	        else{
    	            res=Math.max(res,j-i+1);
    	            visited[str.charAt(j)]=true;
    	        }
    	    }
    	} 
    	return res; 
    } 
    
    public static void main(String args[]) 
    { 
        String str = "geeksforgeeks"; 
	    int len = longestDistinct(str);  // OUTPUT : 7
        System.out.print("The length of longest distinct characters substring is "+ len); 
    } 
} 






// Naive Code O(n3) : 

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static boolean areDistinct(String str, int i, int j) 
    { 
    	boolean visited[]=new boolean[256]; 
    
    	for (int k = i; k <= j; k++) { 
    		if (visited[str.charAt(k)] == true) 
    			return false; 
    		visited[str.charAt(k)] = true; 
    	} 
    	return true; 
    } 

    static int longestDistinct(String str) 
    { 
    	int n = str.length(); 
    	int res = 0;
    	for (int i = 0; i < n; i++) 
    		for (int j = i; j < n; j++) 
    			if (areDistinct(str, i, j)) 
    				res = Math.max(res, j - i + 1); 
    	return res; 
    } 
    
    public static void main(String args[]) 
    { 
        String str = "geeksforgeeks"; 
	    int len = longestDistinct(str);  // OUTPUT : 7
        System.out.print("The length of longest distinct characters substring is "+ len);
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
    static int fact(int n) 
    { 
        return (n <= 1) ? 1 : n * fact(n - 1); 
    } 
    
    static int lexRank(String str) 
    { 
        int res = 1; 
        int n=str.length();
        int mul= fact(n);
        int[] count=new int[CHAR];
        for(int i=0;i<n;i++)
            count[str.charAt(i)]++;
        for(int i=1;i<CHAR;i++)
            count[i]+=count[i-1];
        for(int i=0;i<n-1;i++){
            mul=mul/(n-i);
            res=res+count[str.charAt(i)-1]*mul;
            for(int j=str.charAt(i);j<CHAR;j++)
                count[j]--;
        }
        return res; 
    } 
    
    public static void main(String args[]) 
    { 
        String str = "STRING"; 
        System.out.print(lexRank(str)); // OUTPUT : 598
    } 
} 
// Efficient Code : O(m+(n-m) * CHAR)  or  since m<n so, 
// Time : O(n * CHAR),  Aux. Space : Θ(CHAR)

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
    static boolean areSame(int CT[],int CP[])
    {
        for(int i=0;i<CHAR;i++){
            if(CT[i]!=CP[i])return false;
        }
        return true;
    }
    
    static boolean isPresent(String txt,String pat)
    {
        int[] CT=new int[CHAR];
        int[] CP=new int[CHAR];
        for(int i=0;i<pat.length();i++) {
            CT[txt.charAt(i)]++;
            CP[pat.charAt(i)]++;
        }
        for(int i=pat.length();i<txt.length();i++) {
            if(areSame(CT,CP))return true;
            CT[txt.charAt(i)]++;
            CT[txt.charAt(i-pat.length())]--;
        }
        return false;
    }
    
    public static void main(String args[]) 
    { 
        String txt = "geeksforgeeks"; 
        String pat = "frog";  
        if (isPresent(txt, pat)) 
            System.out.println("Anagram search found"); 
        else
            System.out.println("Anagram search not found"); 
    } 
} 






// Naive Code : O((n-m+1)*m)

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
    static boolean areAnagram(String pat, String txt,int i) 
    { 
        int[] count=new int[CHAR];
        for(int j=0; j<pat.length(); j++)
        {
            count[pat.charAt(j)]++;
            count[txt.charAt(i+j)]--;
        }
        for(int j=0; j<CHAR; j++)
        {
            if(count[j]!=0)
                return false;
        }
        return true;
    } 
    
    static boolean isPresent(String txt,String pat)
    {
        int n=txt.length();
        int m=pat.length();
        for(int i=0;i<=n-m;i++)
        {
            if(areAnagram(pat,txt,i))
                return true;
        }
        return false;
    }
    
    public static void main(String args[]) 
    { 
        String txt = "geeksforgeeks"; 
        String pat = "frog";  
        if (isPresent(txt, pat)) 
            System.out.println("Anagram search found"); 
        else
            System.out.println("Anagram search not found"); 
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 
    
    static boolean areRotations(String s1,String s2)
    {
        if(s1.length()!=s2.length())
            return false;
            
        return ((s1+s1).indexOf(s2)>=0);
    }

    public static void main(String args[]) 
    {   
        String s1 = "ABCD";String s2="CDAB";
        
        if(areRotations(s1,s2)){
            System.out.println("Strings are rotations of each other");
        }
        else{
            System.out.println("Strings are not rotations of each other");
        }  
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 

    static void fillLPS(String str, int lps[])
    {
        int n=str.length(),len=0;
        lps[0]=0;
        int i=1;
        while(i<n){
            if(str.charAt(i)==str.charAt(len))
            {len++;lps[i]=len;i++;}
            else
            {if(len==0){lps[i]=0;i++;}
                else{len=lps[len-1];}
            }
        }
    }

    static void KMP(String pat,String txt)
    {
        int N=txt.length();
        int M=pat.length();
        int[] lps=new int[M];
        fillLPS(pat,lps);
        int i=0,j=0;
        while(i<N){
            if(pat.charAt(j)==txt.charAt(i)){i++;j++;}
    
            if (j == M) { 
                System.out.println("Found pattern at index " + (i - j));
                j = lps[j - 1]; 
            } 
            else if (i < N && pat.charAt(j) != txt.charAt(i)) { 
                if (j == 0) 
                    i++;
                else
                    j = lps[j - 1];  
            }
        }
    }

    public static void main(String args[]) 
    {   String txt = "ababcababaad",pat="ababa";
        KMP(pat,txt);
    }  
     
} 
// Efficient Code O(n)

import java.util.*;
import java.io.*;
  
class GFG { 
  
    static void fillLPS(String str, int lps[])
    {
        int n=str.length(),len=0;
        lps[0]=0;
        int i=1;
        while(i<n){
            if(str.charAt(i)==str.charAt(len))
            {len++;lps[i]=len;i++;}
            else
            {if(len==0){lps[i]=0;i++;}
                else{len=lps[len-1];}
            }
        }
    }
  
    public static void main(String args[]) 
    {   String txt = "abacabad";int[] lps=new int[txt.length()];
        fillLPS(txt,lps);
        for(int i=0;i<txt.length();i++){
            System.out.print(lps[i]+" ");
        } 
    } 
} 




// Naive Code O(n^3)

import java.util.*;
import java.io.*;
  
class GFG { 

    static int longPropPreSuff(String str, int n)
    {
        for(int len=n-1;len>0;len--){
            boolean flag=true;
            for(int i=0;i<len;i++)
                if(str.charAt(i)!=str.charAt(n-len+i))
                    flag=false;
                    
            if(flag==true)
                return len;
        }
        return 0;
    }

    static void fillLPS(String str, int lps[]){
        for(int i=0;i<str.length();i++){
        lps[i]=longPropPreSuff(str,i+1);
        }
    }
  
    public static void main(String args[]) 
    {   String txt = "abacabad";int[] lps=new int[txt.length()];
        fillLPS(txt,lps);
        for(int i=0;i<txt.length();i++){
            System.out.print(lps[i]+" ");
    }  
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 
    static final int d=256;
    static final int q=101;   
    static void RBSearch(String pat,String txt,int M, int N)
    {
        //Compute (d^(M-1))%q
        int h=1;
        for(int i=1;i<=M-1;i++)
            h=(h*d)%q;
        
        //Compute p and to
        int p=0,t=0;
        for(int i=0;i<M;i++){
            p=(p*d+pat.charAt(i))%q;
            t=(t*d+txt.charAt(i))%q;
        }
        
        for(int i=0;i<=(N-M);i++){
           //Check for hit
           if(p==t){
               boolean flag=true;
               for(int j=0;j<M;j++)
                    if(txt.charAt(i+j)!=pat.charAt(j)){flag=false;break;}
                if(flag==true)System.out.print(i+" ");
           }
           //Compute ti+1 using ti
           if(i<N-M){
               t=((d*(t-txt.charAt(i)*h))+txt.charAt(i+M))%q;
            if(t<0)t=t+q;
           }
        }
        
    }
  
    public static void main(String args[]) 
    {   String txt = "GEEKS FOR GEEKS";String pat="GEEK";
        System.out.print("All index numbers where pattern found: ");
        RBSearch(pat,txt,4,15);  
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 
       
    static void patSearchinng(String txt,String pat)
    {
        int m=pat.length();
        int n=txt.length();
        for(int i=0;i<=(n-m); )
        {
            int j;
            for(j=0;j<m;j++)
                if(pat.charAt(j)!=txt.charAt(i+j))
                    break;
            
            if(j==m)
                System.out.print(i+" ");
            if(j==0)
                i++;
            else
                i=(i+j);
        }
    }
  
    public static void main(String args[]) 
    {   String txt = "ABCABCD";String pat="ABCD";
        System.out.print("All index numbers where pattern found: ");
        patSearchinng(txt,pat);  
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 
       
    static void patSearchinng(String txt,String pat)
    {
        int m=pat.length();
        int n=txt.length();
        for(int i=0;i<=(n-m);i++){
      	    int j;
            for(j=0;j<m;j++)
                if(pat.charAt(j)!=txt.charAt(i+j))
              	    break;
            
        if(j==m)
            System.out.print(i+" ");
        }
    }
  
    public static void main(String args[]) 
    {   String txt = "ABCABCD";String pat="ABCD";
        System.out.print("All index numbers where pattern found: ");
        patSearchinng(txt,pat);  
    } 
} 
m -> Pattern length
n -> Text length
1 <= m <=n
---------------------------------------------------------------------------------------------------

// NO PREPROCESSING

Naive : O((n-m+1)*m)

Naive (When all characters of Pattern are distinct) : O(n)
---------------------------------------------------------------------------------------------------

// PREPROCESS PATTERN
  
Rabin Karp : O((n-m+1)*m)  // But, better then naive on average

KMP Algorithm : O(n)
---------------------------------------------------------------------------------------------------

// PREPROCESS TEXT
  
Suffix Tree : O(m)
// Efficient Approach :
// NOTE : The code doesn’t handle the cases when the string starts with space. 

import java.util.*;
import java.io.*;
  
class GFG { 
       
    static void reverse(char str[],int low, int high)
    {
        while(low<=high)
        {
            //swap
            char temp=str[low];
            str[low]=str[high];
            str[high]=temp;

            low++;
            high--;
        }
    }

    static void reverseWords(char str[],int n){
    int start=0;
    for(int end=0;end<n;end++){
        if(str[end]==' '){
            reverse(str,start,end-1);
            start=end+1;
        }
    }
    reverse(str,start,n-1);
    reverse(str,0,n-1);
    }
  
    public static void main(String args[]) 
    {   String s = "Welcome to Gfg";int n=s.length();
        char[] str = s.toCharArray();
        System.out.println("After reversing words in the string:");
        reverseWords(str,n);
        System.out.println(str);  
    } 
} 
// One Traversal
// Efficient Approach-1 : Time Complexity : O(n)
 
    static final int CHAR=256;
    static int nonRep(String str) 
    {
        int[] fI=new int[CHAR];
        Arrays.fill(fI,-1);
    
        for(int i=0;i<str.length();i++){
            if(fI[str.charAt(i)]==-1)
            fI[str.charAt(i)]=i;
            else
            fI[str.charAt(i)]=-2;
        }
        int res=Integer.MAX_VALUE;
        for(int i=0;i<CHAR;i++){
            if(fI[i]>=0)res=Math.min(res,fI[i]);
        }
        return (res==Integer.MAX_VALUE)?-1:res;
    }
 
 
// Two Traversal
// Better Approach : Time Complexity : O(n) 
 
    static final int CHAR=256;
    static int nonRep(String str) 
    {
        int[] count=new int[CHAR];
        for(int i=0;i<str.length();i++){
            count[str.charAt(i)]++;
        }
        for(int i=0;i<str.length();i++){
            if(count[str.charAt(i)]==1)return i;
        }
        return -1;
    } 
 
 
// Naive Code : Time Complexity : O(n^2)
 
    static int nonRep(String str) 
    {
        for(int i=0;i<str.length();i++){
            boolean flag=false;
            for(int j=0;j<str.length();j++){
                if(i!=j&&str.charAt(i)==str.charAt(j)){
                    flag=true;
                    break;
                }
            }
            if(flag==false)return i;
        }
        return -1;
    }
// Efficient Approach-2 : Time & Space similar to previous method

    static final int CHAR=256;
    static int leftMost(String str) 
    {
        boolean[] visited=new boolean[CHAR];
        int res=-1;
        for(int i=str.length()-1;i>=0;i--){
            if(visited[str.charAt(i)])
            res=i;
            else
            visited[str.charAt(i)]=true;
        }
        
        return res;
    } 



// One Traversal
// Efficient Approach-1 : Time Complexity : O(n + CHAR), Auxiliary Space : O(CHAR)

    static final int CHAR=256;
    static int leftMost(String str) 
    {
        int[] fIndex=new int[CHAR];
        Arrays.fill(fIndex,-1);
        int res=Integer.MAX_VALUE;
        for(int i=0;i<str.length();i++){
            int fi=fIndex[str.charAt(i)];
            if(fi==-1)
            fIndex[str.charAt(i)]=i;
            else
            res=Math.min(res,fi);
        }
        
        return (res==Integer.MAX_VALUE)?-1:res;
    } 



// Better Approach : Time Complexity : O(n) but requires two loops for input string 

    static final int CHAR=256;
    static int leftMost(String str) 
    {
        int[] count=new int[CHAR];
        for(int i=0;i<str.length();i++){
            count[str.charAt(i)]++;
        }
        for(int i=0;i<str.length();i++){
            if(count[str.charAt(i)]>1)return i;
        }
        return -1;
    }


// Naive Code : Time Complexity : O(n^2)

    static int leftMost(String str) 
    {
        for(int i=0;i<str.length();i++){
            for(int j=i+1;j<str.length();j++){
                if(str.charAt(i)==str.charAt(j))return i;
            }
        }
        return -1;
    }
// Efficient : Time Complexity : O(n)
 
import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
        
    static boolean areAnagram(String s1, String s2) 
    { 
       if (s1.length() != s2.length()) 
            return false; 
  
        int[] count=new int[CHAR];
        for(int i=0;i<s1.length();i++){
            count[s1.charAt(i)]++;
            count[s2.charAt(i)]--;
        }
    
        for(int i=0;i<CHAR;i++){
            if(count[i]!=0)return false;
        }
        return true;
    }
  
    public static void main(String args[]) 
    { 
        String str1 = "abaac"; 
        String str2 = "aacba";  
        if (areAnagram(str1, str2)) 
            System.out.println("The two strings are" + " anagram of each other"); 
        else
            System.out.println("The two strings are not" + " anagram of each other"); 
    } 
} 
 
 

// Naive : Time Complexity : Θ(nlogn)
 
    static boolean areAnagram(String s1, String s2) 
    { 
       
        if (s1.length() != s2.length()) 
            return false; 
  
       char a1[]=s1.toCharArray();
        Arrays.sort(a1);
        s1=new String(a1);
        char a2[]=s2.toCharArray();
        Arrays.sort(a2);
        s2=new String(a2);
        
        return s1.equals(s2);
    } 
// Iterative Solution : Time Complexity : O(n+m), Space Complexity : Θ(1)

    static boolean isSubSeq(String s1, String s2, int n, int m){
        int j = 0;
        for(int i = 0; i < n && j < m; i++){
            if(s1.charAt(i) == s2.charAt(j))
            j++;
        }
        
        return j == m;
    }



// Recursive Solution : Time Complexity : O(n+m), Space Complexity : Θ(n+m)

    static boolean isSubSeq(String s1, String s2, int n, int m){
        if( m == 0 )
            return true;
        
        if( n == 0 )
            return false;
            
        if ( s1.charAt(n-1) == s2.charAt(m-1) )
            return isSubSeq(s1, s2, n-1, m-1);
        
        else
            return isSubSeq(s1, s2, n-1, m);
    }
// Efficient : Time Complexity : O(n), Space Complexity : Θ(1)

    static boolean isPalindrome(String str)
    {
 
        // Pointers pointing to the beginning
        // and the end of the string
        int begin = 0, end = str.length() - 1;
 
        // While there are characters to compare
        while (begin < end) {
 
            // If there is a mismatch
            if (str.charAt(begin) != str.charAt(end))
                return false;
 
            // Increment first pointer and
            // decrement the other
            begin++;
            end--;
        }
 
        // Given string is a palindrome
        return true;
    }


// Naive : Time Complexity : Θ(n), Space Complexity : Θ(n)

    static boolean isPalindrome(String str)
    {
      StringBuilder rev = new StringBuilder(str);
      rev.reverse();  // StringBuilder is mutable & has a function called reverse
      
      return str.equals(rev.toString());
    }
// Time Complexity : O(r * log(max - min) * logC)

import java.util.Arrays;

public class MedianInRowSorted
{
    static public int matMed(int mat[][], int r ,int c)
    {
    	int min = mat[0][0], max = mat[0][c-1];
    	for (int i=1; i<r; i++)
    	{
    		if (mat[i][0] < min)
    			min = mat[i][0];
    
    		if (mat[i][c-1] > max)
    			max = mat[i][c-1];
    	}
    
    	int medPos = (r * c + 1) / 2;
    	while (min < max)
    	{
    		int mid = (min + max) / 2;
    		int midPos = 0;
            int pos = 0;
    		for (int i = 0; i < r; ++i){
    			    pos = Arrays.binarySearch(mat[i],mid);
                    
                    if(pos < 0)
                        pos = Math.abs(pos) - 1;
                      
                    
                    else
                    {
                        while(pos < mat[i].length && mat[i][pos] == mid)
                            pos += 1;
                    }
                      
                    midPos = midPos + pos;
    		}
    		if (midPos < medPos)
    			min = mid + 1;
    		else
    			max = mid;
    	}
    	return min;
    }

    public static void main(String[] args)
    {
    	int r = 3, c = 5;
    	int m[][]= { {5,10,20,30,40}, {1,2,3,4,6}, {11,13,15,17,19} };
    	System.out.println("Median is " + matMed(m, r, c)); 
    	
    }
}
// Efficient Code : Time Complexity : O(R + C)
 
import java.util.*;
import java.io.*;
 
class GFG 
{ 
	static int R = 4, C = 4;

	static void search(int mat[][], int x)
	{
		int i  = 0, j = C - 1;

		while(i < R && j >= 0)
		{
			if(mat[i][j] == x)
			{
				System.out.println("Found at (" + i + ", " + j + ")");
				return;
			}
			else if(mat[i][j] > x)
			{
				j--;
			}
			else
			{
				i++;
			}
		}
		System.out.println("Not Found");
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{10, 20, 30, 40},
    				   {15, 25, 35, 45},
    				   {27, 29, 35, 45},
    				   {32, 33, 39, 50}};
    	int x = 29;	   

    	search(arr, x);

		
    } 
}
 
 
 
 
// Naive Code : Time Complexity : O(R * C)
 
	static int R = 4, C = 4;

	static void search(int mat[][], int x)
	{
		for(int i = 0; i < R; i++)
		{
			for(int j = 0; j < C; j++)
			{
				if(mat[i][j] == x)
				{
					System.out.println("Found at (" + i + ", " + j + ")");
					
					return;
				}
			}
		}

		System.out.println("Not Found");
	}
import java.util.*;
import java.io.*;

class GFG 
{ 
	static void printSpiral(int mat[][], int R, int C)
	{
		int top = 0, left = 0, bottom = R - 1, right = C - 1;

		while(top <= bottom && left <= right)
		{
			for(int i = left; i <= right; i++)
				System.out.print(mat[top][i] + " ");

			top++;

			for(int i = top; i <= bottom; i++)
				System.out.print(mat[i][right] + " ");
			
			right--;

			if(top <= bottom){
			for(int i = right; i >= left; i--)
				System.out.print(mat[bottom][i] + " ");

			bottom--;
			}

			if(left <= right){
			for(int i = bottom; i >= top; i--)
				System.out.print(mat[i][left] + " ");

			left++;
			}			
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	printSpiral(arr, 4, 4);
    } 
}
// Efficient Code : Time Complexity : O(n^2), Auxiliary Space : O(1)
 
import java.util.*;
import java.io.*;
 
class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}
	
	static void swap2(int low, int high, int i, int mat[][])
	{
	    	int temp = mat[low][i];
			mat[low][i] = mat[high][i];
			mat[high][i] = temp;
	}

	static void rotate90(int mat[][])
	{
		// Transpose
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
      
		// Reverse columns		
		for(int i = 0; i < n; i++)
		{
		    int low = 0, high = n - 1;
		    
		    while(low < high)
		    {
		        swap2(low, high, i, mat);
		        
		        low++;
		        high--;
		    }
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	rotate90(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    }
}
 
 
 
 
// Naive Code : Time Complexity : O(n^2), Space Complexity : O(n^2)
 
	static int n = 4;

	static void rotate90(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				temp[n - j - 1][i] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				mat[i][j] = temp[i][j];

	}

// last column becomes first row
// second last column becomes second row
// Efficient Code : Without Using Auxiliary Array

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

class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}

	static void transpose(int mat[][])
	{

		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	transpose(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    } 
}




// Naive Code : 

	static int n = 4;

	static void transpose(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy
				temp[i][j] = mat[j][i]; // temp[i][j] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy back to original array
				mat[i][j] = temp[i][j];

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

class GFG 
{ 
	static int R = 4, C = 4;

	static void bTraversal(int mat[][])
	{
		if(R == 1)
		{
			for(int i = 0; i < C; i++)
				System.out.print(mat[0][i] + " ");
		}
		else if(C == 1)
		{
			for(int i = 0; i < R; i++)
				System.out.print(mat[i][0] + " ");
		}
		else
		{
			for(int i = 0; i < C; i++)
				System.out.print(mat[0][i] + " ");
			for(int i = 1; i < R; i++)
				System.out.print(mat[i][C - 1] + " ");
			for(int i = C - 2; i >= 0; i--)
				System.out.print(mat[R - 1][i] + " ");
			for(int i = R - 2; i >= 1; i--)
				System.out.print(mat[i][0] + " ");
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	bTraversal(arr);
    } 
}
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int R = 4, C = 4;
	static void printSnake(int mat[][])
	{
		for(int i = 0; i < R; i++)
		{
			if(i % 2 == 0)
			{
				for(int j = 0; j < C; j++)
					System.out.print(mat[i][j] + " ");
			}
			else
			{
				for(int j = C - 1; j >= 0; j--)
					System.out.print(mat[i][j] + " ");
			}
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	printSnake(arr);
    } 
}
// Efficient : (HASHING Using Prefix Sum) : Time Complexity: O(n), Auxiliary Space: O(n)

class LargestSubArray {

	// This function Prints the starting and ending
	// indexes of the largest subarray with equal
	// number of 0s and 1s. Also returns the size
	// of such subarray.

	int findSubArray(int arr[], int n)
	{
		int sum = 0;
		int maxsize = -1, startindex = 0;
		int endindex = 0;

		// Pick a starting point as i

		for (int i = 0; i < n - 1; i++) {
			sum = (arr[i] == 0) ? -1 : 1;

			// Consider all subarrays starting from i

			for (int j = i + 1; j < n; j++) {
				if (arr[j] == 0)
					sum += -1;
				else
					sum += 1;

				// If this is a 0 sum subarray, then
				// compare it with maximum size subarray
				// calculated so far

				if (sum == 0 && maxsize < j - i + 1) {
					maxsize = j - i + 1;
					startindex = i;
				}
			}
		}
		endindex = startindex + maxsize - 1;
		if (maxsize == -1)
			System.out.println("No such subarray");
		else
			System.out.println(startindex + " to " + endindex);

		return maxsize;
	}

	/* Driver program to test the above functions */

	public static void main(String[] args)
	{
		LargestSubArray sub;
		sub = new LargestSubArray();
		int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
		int size = arr.length;

		sub.findSubArray(arr, size);
	}
}
// A Java program to find
// if there is a zero sum subarray
import java.util.HashSet;
import java.util.Set;

class ZeroSumSubarray
{
	// Returns true if arr[]
	// has a subarray with sero sum
	static Boolean subArrayExists(int arr[])
	{
		// Creates an empty hashset hs
		Set<Integer> hs = new HashSet<Integer>();

		// Initialize sum of elements
		int sum = 0;

		// Traverse through the given array
		for (int i = 0; i < arr.length; i++)
		{
			// Add current element to sum
			sum += arr[i];

			// Return true in following cases
			// a) Current element is 0
			// b) sum of elements from 0 to i is 0
			// c) sum is already present in hash map
			if (arr[i] == 0
				|| sum == 0
				|| hs.contains(sum))
				return true;

			// Add sum to hash set
			hs.add(sum);
		}

		// We reach here only when there is
		// no subarray with 0 sum
		return false;
	}

	// Driver code
	public static void main(String arg[])
	{
		int arr[] = { -3, 2, 3, 1, 6 };
		if (subArrayExists(arr))
			System.out.println(
				"Found a subarray with 0 sum");
		else
			System.out.println("No Such Sub Array Exists!");
	}
}
// Java program to determine if array arr[]
// can be split into three equal sum sets.

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

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

public class GFG {
	
	// Function to determine if array arr[]
	// can be split into three equal sum sets.
	static int findSplit(int []arr, int n)
	{
		int i;
	
		// variable to store prefix sum
		int preSum = 0;
	
		// variables to store indices which
		// have prefix sum divisible by S/3.
		int ind1 = -1, ind2 = -1;
	
		// variable to store sum of
		// entire array.
		int S;
	
		// Find entire sum of the array.
		S = arr[0];
		for (i = 1; i < n; i++)
			S += arr[i];
	
		// Check if array can be split in
		// three equal sum sets or not.
		if(S % 3 != 0)
			return 0;
		
		// Variables to store sum S/3
		// and 2*(S/3).
		int S1 = S / 3;
		int S2 = 2 * S1;
	
		// Loop until second last index
		// as S2 should not be at the last
		for (i = 0; i < n-1; i++)
		{
			preSum += arr[i];
			
		// If prefix sum is equal to S/3
		// store current index.
			if (preSum == S1 && ind1 == -1)
				ind1 = i;
			
		// If prefix sum is equal to 2*(S/3)
		// store current index.
			else if(preSum == S2 && ind1 != -1)
			{
				ind2 = i;
				
				// Come out of the loop as both the
				// required indices are found.
				break;
			}
		}
	
		// If both the indices are found
		// then print them.
		if (ind1 != -1 && ind2 != -1)
		{
			System.out.print("(" + ind1 + ", "
							+ ind2 + ")");
			return 1;
		}
	
		// If indices are not found return 0.
		return 0;
	}
	
	// Driver code
	public static void main(String args[])
	{
		int []arr = { 1, 3, 4, 0, 4 };
		int n = arr.length;
		if (findSplit(arr, n) == 0)
			System.out.print("-1");
	}
}

// Output: (1, 2)
import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxOcc(int L[], int R[], int n, int maxx)
    {	
	    	int arr[] = new int[1000000];

	    	for(int i = 0; i < n; i++)
	    	{
	    		arr[L[i]]++;

	    		arr[R[i] + 1]-=1; // arr[R[i] + 1]--;
	    	}

	    	int maxm = arr[0], res = 0;

	    	for(int i = 1; i < maxx; i++) // maxx = 1000000
	    	{
	    		arr[i] += arr[i - 1];

	    		if(maxm < arr[i])
	    		{
	    			maxm = arr[i];

	    			res = i;
	    		}
	    	}

	    	return res;
    }
    public static void main(String args[]) 
    { 
       int L[] = {1, 2, 3}, R[] = {3, 5, 7}, n = 3;

      System.out.println(maxOcc(L, R, n)); 
    } 
}
// Efficient Method : Time Complexity : O(n), Auxilliary space : O(1)

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

class GFG 
{ 
    static boolean checkEquilibrium(int arr[], int n)
    {
    	int sum = 0;

    	for(int i = 0; i < n; i++)
    	{
    		sum += arr[i];
    	}

    	int l_sum = 0;

    	for(int i = 0; i < n; i++)
    	{
    		if(l_sum == sum - arr[i])
    			return true;

    		l_sum += arr[i];

    		sum -= arr[i];
    	}

    	return false;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {3, 4, 8, -9, 20, 6}, n = 6;

       System.out.println(checkEquilibrium(arr, n));
    } 
}




// Naive Method : Time Complexity : O(n^2)

    static boolean checkEquilibrium(int arr[], int n)
    {
    	for(int i  = 0; i < n; i++)
    	{
    		int l_sum = 0, r_sum = 0;

    		for(int j = 0; j < i; j++)
    			l_sum += arr[j];

    		for(int j = i + 1; j < n; j++)
    			r_sum += arr[j];

    		if(l_sum == r_sum)
    			return true;
    	}

    	return false;
    }
import java.util.*;
import java.io.*;

class GFG 
{ 
	// For preprocessing : O(n)
    static int[] preSum(int arr[], int n)
    {	
    	int prefix_sum[] = new int[n];

    	prefix_sum[0] = arr[0];

    	for(int i = 1; i < n; i++)
    	{
    		prefix_sum[i] = prefix_sum[i - 1] + arr[i];
    	}
    	
    	return prefix_sum;
    }

	// For answer queries : O(1)
    static int getSum(int prefix_sum[], int l, int r)
    {
    	if(l != 0)
    		return prefix_sum[r] - prefix_sum[l - 1];
    	else
    		return prefix_sum[r];
    }
    
    public static void main(String args[]) 
    { 
       int arr[] = {2, 8, 3, 9, 6, 5, 4}, n = 7;

       int prefix_sum[] = preSum(arr, n);

       System.out.println(getSum(prefix_sum, 1, 3));
       
       System.out.println(getSum(prefix_sum, 0, 2));
       
    } 

}
// Time Complexity : O(n), Auxiliary space : O(1)

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

class GFG 
{ 

    static void printGroups(int arr[], int n)
    {
    	for(int i = 1; i < n; i++)
    	{
    		if(arr[i] != arr[i - 1])
    		{
    			if(arr[i] != arr[0])
                    System.out.print("From " + i + " to ");
    			else
                    System.out.println(i - 1);
    		}
    	}

    	if(arr[n - 1] != arr[0])
            System.out.println(n-1);
    }

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

       printGroups(arr, n);
    } 
}
// Efficient Solution : Time Complexity : O(n)

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

class GFG 
{ 
    static int findMajority(int arr[], int n)
    {
    	int res = 0, count = 1;

    	for(int i = 1; i < n; i++)
    	{
    		if(arr[res] == arr[i])
    			count++;
    		else 
    			count --;

    		if(count == 0)
    		{
    			res = i; count = 1;
    		}
    	}

    	count = 0;

    	for(int i = 0; i < n; i++)
    		if(arr[res] == arr[i])
    			count++;

    	if(count <= n /2)
    		res = -1;

    	return res; 
    }


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

       System.out.println(findMajority(arr, n));  // Output : 3
    } 
}


// Naive Solution : Time Complexity : O(n^2)

    static int findMajority(int arr[], int n)
    {
    	for(int i = 0; i < n; i++)
    	{
    		int count = 1;

    		for(int j = i + 1; j < n; j++)
    		{
    			if(arr[i] == arr[j])
    				count++;
    		}

    		if(count > n / 2)
    			return i;
    	}

    	return -1;
    }
// Efficient Method (Based on KADANE's ALGORITHM) : Time Complexity : O(n)

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

class GFG 
{ 
  	// STANDARD KADANE's ALGORITHM
    static int normalMaxSum(int arr[], int n)
    {
    	int res = arr[0];

    	int maxEnding = arr[0];

    	for(int i = 1; i < n; i++)
    	{
    		maxEnding = Math.max(maxEnding + arr[i], arr[i]);

    		res = Math.max(maxEnding, res);
    	}
    	
    	return res;
    }

    static int overallMaxSum(int arr[], int n)
    {
      	// Normal Sum
    	int max_normal = normalMaxSum(arr, n);

    	if(max_normal < 0)
    		return max_normal;

    	int arr_sum = 0;
		// Circular Sum
    	for(int i = 0; i < n; i++)
    	{
    		arr_sum += arr[i];

    		arr[i] = -arr[i];
    	}

    	int max_circular = arr_sum + normalMaxSum(arr, n);

    	return Math.max(max_circular, max_normal);
    }

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

       System.out.println(overallMaxSum(arr, n));
    } 
}



// Naive Method : Time Complexity : O(n^2)

    static int maxCircularSum(int arr[], int n)
    {
    	int res = arr[0];

    	for(int i = 0; i < n; i++)
    	{
    		int curr_max = arr[i];
    		int curr_sum = arr[i];

    		for(int j = 1; j < n; j++)
    		{
    			int index = (i + j) % n;

    			curr_sum += arr[index];

    			curr_max = Math.max(curr_max, curr_sum);
    		}

    		res = Math.max(res, curr_max);
    	}
    	return res;
    }
// Efficient Method : Time Complexity : O(n)
// Based on KADANE's ALGORITHM

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

class GFG 
{ 
    static int maxEvenOdd(int arr[], int n)
    {
    	int res = 1;
    	int curr = 1;

    	for(int i = 1; i < n; i++)
    	{
    			if((arr[i] % 2 == 0 && arr[i - 1] % 2 != 0)
    			   ||(arr[i] % 2 != 0 && arr[i - 1] % 2 == 0))
    				{
    					curr++;

    					res = Math.max(res, curr);
    				}
    				else
    					curr = 1;
    	}
    	
    	return res;
    }

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

       System.out.println(maxEvenOdd(arr, n));
    } 
}




// Naive : Time Complexity : O(n^2)

    static int maxEvenOdd(int arr[], int n)
    {
    	int res = 1;

    	for(int i = 0; i < n; i++)
    	{
    		int curr = 1;

    		for(int j = i + 1; j < n; j++)
    		{
    			if((arr[j] % 2 == 0 && arr[j - 1] % 2 != 0)
    			   ||(arr[j] % 2 != 0 && arr[j - 1] % 2 == 0))
    				curr++;
    			else
    				break;
    		}

    		res = Math.max(res, curr);
    	}
    	
    	return res;
    }
// Efficient Method (KADANE's ALGORITHM) : Time Complexity : O(n)

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

class GFG 
{ 
    static int maxSum(int arr[], int n)
    {
    	int res = arr[0];

    	int maxEnding = arr[0];

    	for(int i = 1; i < n; i++)
    	{
    		maxEnding = Math.max(maxEnding + arr[i], arr[i]);

    		res = Math.max(maxEnding, res);
    	}
    	
    	return res;
    }

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

       System.out.println(maxSum(arr, n));
    } 
}


// Naive : Time Complexity : O(n^2)

	static int maxSum(int arr[], int n)
    {
    	int res = arr[0];

    	for(int i = 0; i < n; i++)
    	{
    		int curr = 0;

    		for(int j = i; j < n; j++)
    		{
    			curr = curr + arr[j];

    			res = Math.max(res, curr);
    		}
    	}
    	
    	return res;
    }
// Efficient Method : Time Complexity : O(n), Auxiliary space : O(1)

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

class GFG 
{ 
    static int maxConsecutiveOnes(int arr[], int n)
    {
    	int res = 0, curr = 0;

    	for(int i = 0; i < n; i++)
    	{
    		if(arr[i] == 0)
    			curr = 0;
    		else
    		{
    			curr++;

    			res = Math.max(res, curr);
    		}
    	}
    	
    	return res;
    }

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

       System.out.println(maxConsecutiveOnes(arr, n)); // Output : 3
    } 
}


// Naive Method : Time Complexity : O(n^2), Auxiliary space : O(1)

    static int maxConsecutiveOnes(int arr[], int n)
    {
    	int res = 0;

    	for(int i = 0; i < n; i++)
    	{
    		int curr = 0;

    		for(int j = i; j < n; j++)
    		{
    			if(arr[j] == 1) curr++;
    			else break;
    		}

    		res = Math.max(res, curr);
    	}
    	
    	return res;
    }
// Efficient Method : Time Complexity : O(n), Auxilliary Space : O(n)

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

class GFG 
{ 
    static int getWater(int arr[], int n)
    {
    	int res = 0;

    	int lMax[] = new int[n];
    	int rMax[] = new int[n];

    	lMax[0] = arr[0];
    	for(int i = 1; i < n; i++)
    		lMax[i] = Math.max(arr[i], lMax[i - 1]);


    	rMax[n - 1] = arr[n - 1];
    	for(int i = n - 2; i >= 0; i--)
    		rMax[i] = Math.max(arr[i], rMax[i + 1]);

    	for(int i = 1; i < n - 1; i++)
    		res = res + (Math.min(lMax[i], rMax[i]) - arr[i]);
    	
    	return res;
    }


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

      System.out.println( getWater(arr, n)); // Output : 6
    } 
}


// Naive Method : Time Complexity : O(n^2)

    static int getWater(int arr[], int n)
    {
    	int res = 0;

    	for(int i = 1; i < n - 1; i++)
    	{
    		int lMax = arr[i];

    		for(int j = 0; j < i; j++)
    			lMax = Math.max(lMax, arr[j]);

    		int rMax = arr[i];

    		for(int j = i + 1; j < n; j++)
    			rMax = Math.max(rMax, arr[j]);

    		res = res + (Math.min(lMax, rMax) - arr[i]);
    	}
    
    	return res; // Output : 6
    }
import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxProfit(int price[], int n)
    {
    	int profit = 0;

    	for(int i = 1; i < n; i++)
    	{
    		if(price[i] > price[i - 1])
    			profit += price[i] - price[i -1];
    	}
    
    	return profit;
    }

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

       System.out.println(maxProfit(arr, n));
    } 
}
import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxProfit(int price[], int start, int end)
    {
    	if(end <= start)
    		return 0;

    	int profit = 0;

    	for(int i = start; i < end; i++)
    	{
    		for(int j = i + 1; j <= end; j++)
    		{
    			if(price[j] > price[i])
    			{
    				int curr_profit = price[j] - price[i] 
    								  + maxProfit(price, start, i - 1)
    								  + maxProfit(price, j + 1, end);

    				profit = Math.max(profit, curr_profit);
    			}
    		}
    	}

    	return profit;
    }

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

       System.out.println(maxProfit(arr, 0, n-1));
    } 
}
import java.util.*;
import java.io.*;

class GFG 
{ 
    static void printFreq(int arr[], int n)
    {
    	int freq = 1, i = 1;

    	while(i < n)
    	{
    		while(i < n && arr[i] == arr[i - 1])
    		{
    			freq++;
    			i++;
    		}

    		System.out.println(arr[i - 1] + " " + freq);

    		i++;
    		freq = 1;
    	}
    }

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

       printFreq(arr, n);
    } 
}
public class Permutation
{
	public static void main(String[] args)
	{
		String str = "ABC";
		int n = str.length();
		Permutation permutation = new Permutation();
		permutation.permute(str, 0, n-1);
	}

	/**
	* permutation function
	* @param str string to calculate permutation for
	* @param l starting index
	* @param r end index
	*/
	private void permute(String str, int l, int r)
	{
		if (l == r)
			System.out.println(str);
		else
		{
			for (int i = l; i <= r; i++)
			{
				str = swap(str,l,i);
				permute(str, l+1, r);
				str = swap(str,l,i);
			}
		}
	}

	/**
	* Swap Characters at position
	* @param a string value
	* @param i position 1
	* @param j position 2
	* @return swapped string
	*/
	public String swap(String a, int i, int j)
	{
		char[] arr = a.toCharArray();
		char temp = arr[i] ;
		arr[i] = arr[j];
		arr[j] = temp;
		return String.valueOf(arr);
	}

}
// Naive recursive solution : Time Complexity : Θ(2^n)

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

class GFG {

	static int countSubsets(int arr[], int n, int sum)
	{
		if(n == 0)
			return sum==0 ? 1 : 0;

		return countSubsets(arr, n-1, sum) + countSubsets(arr, n-1, sum - arr[n-1]);
	}

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

		System.out.println(countSubsets(arr, n, sum));
	}
}
// Time Complexity : O(n)

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

class GFG 
{ 
    static int check(int n, int k)
    {
    	if(n == 1)
    		return 0;
    	else
    		return (check(n - 1, k) + k) % n;
    }

    static int josephus(int n, int k)
    {
    	return check(n, k) + 1;
    }
      
    public static void main(String args[]) 
    { 
        System.out.println(josephus(5, 3));  
    } 
}
import java.util.*;
import java.io.*;

class GFG 
{ 
    static void ToH(int n, char A, char B, char C) 
    { 
        if (n == 1) 
        { 
            System.out.println("Move 1 from " +  A + " to " + C); 
            return; 
        } 
        ToH(n-1, A, C, B); 
        System.out.println("Move " + n + " from " +  A + " to " + C); 
        ToH(n-1, B, A, C); 
    } 
   
    public static void main(String args[]) 
    { 
        int n = 2; 
        ToH(n, 'A', 'B', 'C');  
    } 
}
import java.io.*;
import java.util.*;

class GFG 
{
	static void printSub(String str, String curr, int index)
	{
		if(index == str.length())
		{
			System.out.print(curr+" ");
			return;
		}

		printSub(str, curr, index + 1);
		printSub(str, curr+str.charAt(index), index + 1);
	}
  
    public static void main(String [] args) 
    {
    	String str = "ABC";
    	
    	printSub(str, "", 0); 
    }
}
import java.io.*;
import java.util.*;

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}
// Sum of Digits Using Recursion : Time Complexity : O(d), Space Complexity : O(d) 
// where d is the number of digits in number

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

class GFG 
{
	static int fun(int n)
	{
		if(n < 10)
			return n;

		return fun(n / 10) + n % 10;
	}
    public static void main(String [] args) 
    {
    	System.out.println(fun(253));
    }
}


// Iterative : Time Complexity : O(d), Space Complexity : O(1) {No Overhead & Less Aux. Space}

	static int getSum(int n)
	{
		int sum = 0;

		while (n != 0) {
			sum = sum + n % 10;
			n = n / 10;
		}

		return sum;
	}
// Time Complexity : O(n), Space Complexity : O(n)

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

class GFG 
{
	static boolean isPalindrome(String str, int start, int end)
	{
		if(start >= end)
			return true;

		return ((str.charAt(start)==str.charAt(end)) && 
			     isPalindrome(str, start + 1, end - 1));
	}
    public static void main(String [] args) 
    {
    	String s = "GeekskeeG";

    	System.out.println(isPalindrome(s, 0, s.length() -1));
    }
}
// Time Complexity : O(n), Space Complexity : O(n)

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

class GFG 
{
	static int getSum(int n)
	{
		if(n == 0)
			return 0;

		return n + getSum(n - 1);
	}
    public static void main(String [] args) 
    {
    	int n = 4;
    	
    	System.out.println(getSum(n));
    }
}
// Time Complexity: O(2^n), Auxiliary Space: O(N).
// Fibonacci Series using Recursion

class fibonacci
{
	static int fib(int n)
	{
      // if (n == 0) return 0;
      // if (n == 1) return 1;
      if (n <= 1)
      	return n;
      
      return fib(n-1) + fib(n-2);
	}
	
	public static void main (String args[])
	{
      int n = 9;
      System.out.println(fib(n));
	}
}
// NON-TAIL RECURSIVE
 
import java.io.*;
import java.util.*;
 
class GFG 
{

	static void fun(int n)
	{
		if(n == 0 || n == 1)
			return 1;
 
		return n*fact(n - 1);
 
	}
  
    public static void main(String [] args) 
    {
    	fun(3);
    }

}




// TAIL RECURSIVE

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

class GFG {

	
	static int fact(int n, int k)
	{
		if(n == 0 || n == 1)
			return k;

		return fact(n - 1, k * n);

	}
  
    public static void main(String [] args) 
    {
    	System.out.println(fact(3, 1));
    }

}
// Example1 : NON-TAIL RECURSIVE

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

class GFG 
{
  	// Print N to 1 Using Recursion
	static void fun(int n)
	{
		if(n == 0)
			return;

		System.out.print(n+" ");

		fun(n - 1);

	}
    public static void main(String [] args) 
    {
    	fun(3);
    }
}

// Example2 : TAIL RECURSIVE

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

class GFG 
{
  	// Print 1 to N Using Recursion
	static void fun(int n, int k)
	{
		if(n == 0)
			return;

		System.out.print(k+" ");

		fun(n - 1, k + 1);

	}
    public static void main(String [] args) 
    {
    	fun(3, 1);
    }
}
// Time Complexity : O(n), Space Complexity : O(n) (Recursive)

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

class GFG {

	
	static void printToN(int n)
	{
		if(n == 0)
			return;
		
		printToN(n - 1);

		System.out.print(n+" ");

	}
    public static void main(String [] args) 
    {
    	int n = 4;

    	printToN(n);
        
    }

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

class GFG {

	
	static void printToN(int n)
	{
		if(n == 0)
			return;
		
		System.out.print(n+" ");
		
		printToN(n - 1);

	}
    public static void main(String [] args) 
    {
    	int n = 4;

    	printToN(n);
        
    }

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

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;
		
		fun(n / 2);

		System.out.println(n % 2);

	}
    public static void main(String [] args) 
    {
        fun(7);
    }

}
class GFG {

	
	static int fun(int n)
	{
		if(n == 1)
			return 0;
		else
			return 1 + fun(n / 2);
	}
    public static void main(String [] args) 
    {
        System.out.println(fun(16));
    }

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

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;

		System.out.println(n);

		fun(n - 1);

		System.out.println(n);
	}
    public static void main(String [] args) 
    {
        fun(3);
    }

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

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;

		fun(n - 1);

		System.out.println(n);
		
		fun(n - 1);
	}
    public static void main(String [] args) 
    {
        fun(3);
    }

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

class GFG {

	
	static void fun1(int n)
	{
		if(n == 0)
			return;

		System.out.println("GFG");

		fun1(n - 1);
	}
    public static void main(String [] args) 
    {
        fun1(2);
    }

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

class GFG {

	
	static void fun1()
	{
		System.out.println("fun1");
	}

	static void fun2()
	{
		System.out.println("Before fun1");

		fun1();

		System.out.println("After fun1");
	}

	public static void main (String[] args) {
		
		System.out.println("Before fun2");

		fun2();

		System.out.println("After fun2");

	}
}
// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(1)

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

public class Main {
	
	static int power(int x, int n)
	{
	    int res = 1;
    
        while(n>0)
        {
          if(n%2 != 0) 
          {
            res = res * x;
            x = x*x;
            n = n/2;
          }
          else 
          {
            x = x*x;
            n = n/2;
          }
        }

		return res; 
	}

	public static void main (String[] args) {
		
		int x = 3, n = 4;

		System.out.println(power(x, n));

	}
}
// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(logn)

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

public class Main {
	
	static int power(int x, int n)
	{
		if(n == 0)
			return 1;

		int temp = power(x, n/2);

		temp = temp * temp;

		if(n % 2 == 0)
			return temp;
		else
			return temp * x; 
	}

	public static void main (String[] args) {
		
		int x = 3, n = 5;

		System.out.println(power(x, n));

	}
}

// Naive Method : Time Complexity : θ(n)
	
	static int power(int x, int n)
	{
	    int res = 1;
    
        for(int i=0; i<n; i++)
        {
          res = res * x;
        }

		return res; 
	}
// Shorter Implementation of the optimized sieve : 

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

public class Main {
	
	static void sieve(int n)
	{
		if(n <= 1)
			return;

		boolean isPrime[] = new boolean[n+1];

		Arrays.fill(isPrime, true);

		for(int i=2; i <= n; i++)
		{
			if(isPrime[i])
			{
        System.out.print(i+" ");
				for(int j = i*i; j <= n; j = j+i)
				{
					isPrime[j] = false;
				}
			}
		}
	}

	public static void main (String[] args) {
		
		int n = 23;

		sieve(n);

	}
}

//Optimized Implementation : Time Complexity : O(nloglogn), Auxiliary Space : O(n)
	
	static void sieve(int n)
	{
		if(n <= 1)
			return;

		boolean isPrime[] = new boolean[n+1];

		Arrays.fill(isPrime, true);

		for(int i=2; i*i <= n; i++)
		{
			if(isPrime[i])
			{
				for(int j = i*i; j <= n; j = j+i) // Replaced 2*i by i*i
				{
					isPrime[j] = false;
				}
			}
		}

		for(int i = 2; i<=n; i++)
		{
			if(isPrime[i])
				System.out.print(i+" ");
		}
	}


//Simple Implementation of Sieve : 
	
	static void sieve(int n)
	{
		if(n <= 1)
			return;

		boolean isPrime[] = new boolean[n+1];

		Arrays.fill(isPrime, true);

		for(int i=2; i*i <= n; i++)
		{
			if(isPrime[i])
			{
				for(int j = 2*i; j <= n; j = j+i) 
				{
					isPrime[j] = false;
				}
			}
		}

		for(int i = 2; i<=n; i++)
		{
			if(isPrime[i])
				System.out.print(i+" ");
		}
	}


//Naive Solution : Time Complexity : O(n(sqrt(n))
  
	static boolean isPrime(int n)
	{
		if(n==1)
			return false;

		if(n==2 || n==3)
			return true;

		if(n%2==0 || n%3==0)
			return false;

		for(int i=5; i*i<=n; i=i+6)
		{
			if(n % i == 0 || n % (i + 2) == 0)
				return false; 
		}

		return true;
	}
	
	static void printPrimes(int n)
	{
		for(int i = 2; i<=n; i++)
		{
			if(isPrime[i])
				System.out.print(i+" ");
		}
	}
// Efficient Code with Sorted Order

	static void printDivisors(int n)
	{
		int i = 1;
      	// Print all divisors from 1(inlcusive) to sqrt(n) (exclusive)
		for(i=1; i*i < n; i++)
		{
			if(n % i == 0)
			{
				System.out.print(i+" ");
			}
		}
		// Print all divisors from sqrt(n)(inlcusive) to n (inclusive)
		for(; i >= 1; i--)
		{
			if(n % i == 0)
			{
				System.out.print((n / i)+" ");
			}
		}
	}

//Efficient Code : Time Complexity: O(sqrt(n)) , Auxiliary Space : O(1)

	static void printDivisors(int n)
	{
		for(int i=1; i*i <= n; i++)
		{
			if(n % i == 0)
			{
				System.out.print(i+" ");

				if(i != n / i)
					System.out.print((n / i)+" ");					
			}
		}
	}

// Naive Solution : Time Complexity : O(n) , Auxiliary Space : O(1)

	static void printDivisors(int n)
	{
		for (int i=1;i<=n;i++)
			if (n%i==0)
				System.out.print(i+" ");
	}
//Prime Factors in java
//More Efficient Solution : Time Complexity : O(sqrt(n))

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

public class Main {

	
	static void printPrimeFactors(int n)
	{
		if(n <= 1)
			return;

		while(n % 2 == 0)
		{
			System.out.print(2+" ");

			n = n / 2;
		}

		while(n % 3 == 0)
		{
			System.out.print(3+" ");

			n = n / 3;
		}

		for(int i=5; i*i<=n; i=i+6)
		{
			while(n % i == 0)
			{
				System.out.print(i+" ");

				n = n / i;
			}

			while(n % (i + 2) == 0)
			{
				System.out.print((i + 2)+" ");

				n = n / (i + 2);
			}
		}

		if(n > 3)
			System.out.print(n+" ");

		System.out.println();
	}

	public static void main (String[] args) {
		
		int n = 450;

		printPrimeFactors(n);

	}
}


//Efficient Code : 


	static void printPrimeFactors(int n)
	{
		if(n <= 1)
			return;

		for(int i=2; i*i<=n; i++)
		{
			while(n % i == 0)
			{
				System.out.print(i+" ");

				n = n / i;
			}
		}

		if(n > 1)
			System.out.print(n+" ");

		System.out.println();
	}



// Naive Method : Time Complexity : O(n^2(logn))

	static boolean isPrime(int n)
	{
		if(n==1)
			return false;

		if(n==2 || n==3)
			return true;

		if(n%2==0 || n%3==0)
			return false;

		for(int i=5; i*i<=n; i=i+6)
		{
			if(n % i == 0 || n % (i + 2) == 0)
				return false; 
		}

		return true;
	}

	static void PrimeFactors(int n)
	{
		for(int i=2; i<n; i++)
		{
		    if(isPrime(i))
		    {
		        int x = i;
		        while(n%x == 0)
		        {
		            System.out.print(i+" ");
		            x = x*i;
		        }
		    }
		}
	}
// Time Complexity: O(N^1/2), Auxilliary Space: O(1)
//More Efficient Code(for large numbers)
//Almost 3x faster than Efficient Solution

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

public class Main {

	static boolean isPrime(int n)
	{
		if(n==1)
			return false;

		if(n==2 || n==3)
			return true;

		if(n%2==0 || n%3==0)
			return false;

		for(int i=5; i*i<=n; i=i+6)
		{
			if(n % i == 0 || n % (i + 2) == 0)
				return false; 
		}

		return true;
	}

  	//DRIVER CODE
	public static void main (String[] args) {
	    
	    //taking input using Scanner class
		Scanner sc=new Scanner(System.in);
		
		int T=sc.nextInt();//input testcases
 
 
		while(T-->0)//while testcase have not been exhausted
		{
		    Solution obj=new Solution ();
		    int N;
		    N=sc.nextInt();//input n
		    if(obj.isPrime(N))
		        System.out.println("Yes");
		    else
		        System.out.println("No");
		    
		}
		
	}
}


//Efficient Code : Time Complexity : O(sqrt(n))
	
	static boolean isPrime(int n)
	{
		if(n==1)
			return false;

		for(int i=2; i*i<=n; i++)
		{
			if(n % i == 0)
				return false; 
		}

		return true;
	}


// Naive Method : Time Complexity : O(n)

	static boolean isPrime(int n)
	{
	    if(n == 1)
	        return false;
		for(int i=2; i<n; i++)
		{
		    if(n%i == 0)
	            return false;
		}
		return true;
	}
// Efficient Solution : Time Complexity : O(log(min(a,b)))
// a * b = gcd(a,b) * lcm(a,b)

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

public class Main {
	
	static int gcd(int a, int b)
	{
		if(b==0)
			return a;

		return gcd(b, a % b);
	}

	static int lcm(int a, int b)
	{
		return (a * b) / gcd(a, b); // constant no. of operations
	}
	
	public static void main (String[] args) {
		
		int a = 4, b = 6;

		System.out.println(lcm(a, b));

	}
}

// Naive Method : Time Complexity : O(a*b-max(a,b))


	static int lcm(int a, int b)
	{
		int res = Math.max(a,b);
		
		while(res > 0)
		{
		    if(res%a == 0 && res%b == 0)
		    {
		        return res;
		    }
		    res++;
		}
		return res;
	}
// Optimised Euclidean Algorithm Code : Time Complexity : O(log(min(a,b)))

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

public class Main {

	static int gcd(int a, int b)
	{
		if(b==0)
			return a;

		return gcd(b, a % b);
	}

	public static void main (String[] args) {
		
		int a = 12, b = 15;

		System.out.println(gcd(a, b));

	}
}

// Euclidean Algorithm Code

  static int gcd(int a, int b)
  {
    while(a!=b)
    {
      if(a > b)
        a = a - b;
      else
        b = b - a; 
    }

    return a;
  }

// Naive Method : Time Complexity : O(min(a,b))

  static int gcd(int a, int b)
  {
    int res = Math.min(a,b);

    while(res > 0)
    {
      if(a%res == 0 && b%res == 0)
      {
        break;
      }
      res--;
    }

    return res;
  }
// Efficient Method : Time Complexity : Θ(logn), Auxiliary Space: O(1)

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

public class Main {

	static int countTrailingZeros(int n)
	{
		int res = 0;

		for(int i=5; i<=n; i=i*5)
		{
			res = res + (n / i);
		}

		return res;
	}

	public static void main (String[] args) {
		
		int number = 251;

		System.out.println(countTrailingZeros(number));

	}
}

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

// Overflow for n=20, as factorial value will be of around 19 digits

static int countTrailingZeros(int n)
{
	int fact = 1;

	for(int i=2; i<=n; i++)
	{
	    fact = fact*i;
	}

	int res = 0;

	while(fact%10 == 0)
	{
	    res++;
	    fact = fact/10;
	}

	return res;
}
// ITERATIVE CODE : Time Complexity : Θ(n), Auxiliary Space : Θ(1)

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

public class Main {

	static int fact(int n)
	{
		int res = 1;

		for(int i=2; i<=n; i++)
		{
			res = res * i;
		}
		return res;
	}

	public static void main (String[] args) {
		
		int number = 5;

		System.out.println(fact(number));

	}
}

// RECURSIVE CODE : Time Complexity : Θ(n), Auxiliary Space : Θ(n) 

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

public class Main {

	
	static int fact(int n)
	{
	    if(n==0)
	        return 1;
		
		return n * fact(n-1);
	}

	public static void main (String[] args) {
		
		int number = 5;

		System.out.println(fact(number));

	}
}
// Time Complexity: O(logN), Auxiliary Space: O(1)
import java.io.*;
import java.util.*;

public class CheckPalindrome {

	static boolean isPal(int n)
	{
		int rev = 0;

		int temp = n;
		// reversed integer is stored in reversed variable
		while(temp != 0)
		{
			int ld = temp % 10;

			rev = rev * 10 + ld;

			temp = temp / 10;
		}	
		// palindrome if orignal and reversed are equal
		return rev==n;
	}

	public static void main (String[] args) {
		
		int number = 4553;

		System.out.println(isPal(number));

	}
}
//Time Complexity : O(d), where 'd' is the digits of number
import java.io.*;
import java.util.*;

public class CountDigits {

	static int countDigits(int num)
	{
		int count = 0;
    
		while(num > 0)
		{
			num = num / 10;
			count++;
		}	
		return count;
	}

	public static void main (String[] args) {
		
		int number = 789;

		System.out.println(countDigits(number));

	}
}
star

Mon Feb 07 2022 15:51:57 GMT+0000 (UTC) https://www.geeksforgeeks.org/largest-subarray-with-equal-number-of-0s-and-1s/

#java #gfg #geeksforgeeks #lecture #arrays #prefixsum #subarrays #hashing
star

Mon Feb 07 2022 15:44:47 GMT+0000 (UTC) https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

#java #gfg #geeksforgeeks #lecture #arrays #prefixsum #subarrays #splitarray
star

Mon Feb 07 2022 15:33:54 GMT+0000 (UTC) https://www.geeksforgeeks.org/split-array-three-equal-sum-subarrays/

#java #gfg #geeksforgeeks #lecture #arrays #prefixsum #subarrays #splitarray
star

Mon Feb 07 2022 15:07:44 GMT+0000 (UTC) https://www.geeksforgeeks.org/maximum-occurred-integer-n-ranges/

#java #gfg #geeksforgeeks #lecture #arrays #prefixsum #maximumoccuredinteger
star

Mon Feb 07 2022 13:18:10 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/max-circular-subarray-sum-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #lecture #arrays #subarray #kadane #circularsubarray #subarraysum #maximumsum
star

Mon Feb 07 2022 13:03:29 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/longest-subarray-of-evens-and-odds/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #lecture #arrays #subarray #kadane #longestevenoddsubarray #maximumlength
star

Mon Feb 07 2022 12:51:57 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1/?track=DSASP-Arrays&batchId=190#

#java #gfg #geeksforgeeks #lecture #arrays #maximumsubarraysum #subarray #kadane
star

Mon Feb 07 2022 12:22:59 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/trapping-rain-water-1587115621/1/?track=DSASP-Arrays&batchId=190#

#java #gfg #geeksforgeeks #lecture #arrays #stock #buysell
star

Sun Feb 06 2022 22:26:48 GMT+0000 (UTC) https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

#java #gfg #geeksforgeeks #lecture #recursion #stringpermutations
star

Sun Feb 06 2022 22:06:53 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/josephus-problem/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #josephusproblem
star

Sun Feb 06 2022 21:54:48 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/tower-of-hanoi-1587115621/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #towerofhanoi #toh
star

Sun Feb 06 2022 21:21:32 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/sum-of-digits-of-a-number/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #digitssum
star

Sun Feb 06 2022 21:03:20 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/fibonacci-using-recursion/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #fibonacci #n-thfibonacci #fibonacciseries
star

Sun Feb 06 2022 20:37:10 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/print-1-to-n-without-using-loops-1587115620/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #lecture #recursion #print1ton using recursion
star

Sun Feb 06 2022 04:24:25 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/primality-test/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #isprime #primalitytest
star

Sun Feb 06 2022 02:48:25 GMT+0000 (UTC) https://practice.geeksforgeeks.org/tracks/DSASP-Mathematics/?batchId=190&tab=2

#java #mathematics #lecture #gfg #geeksforgeeks #factorial #iterative #recursive
star

Sun Feb 06 2022 02:25:06 GMT+0000 (UTC) https://www.geeksforgeeks.org/program-count-digits-integer-3-different-methods/

#java #mathematics #lecture #gfg #geeksforgeeks #countdigits

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension