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());
    }
class Solution 
{
    //Function to find minimum number of operations that are required 
    //to make the matrix beautiful.
    static int findMinOperation(int matrix[][], int n)
    {
        int sumRow[] = new int[n];
        int sumCol[] = new int[n];
        Arrays.fill(sumRow, 0);
        Arrays.fill(sumCol, 0);
        
        //calculating sumRow[] and sumCol[] array.
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                sumRow[i] += matrix[i][j];
                sumCol[j] += matrix[i][j];
                  
            }
        }
        
        //finding maximum sum value in either row or in column.
        int maxSum = 0;
        for (int i = 0; i < n; ++i)
        {
            maxSum = Math.max(maxSum, sumRow[i]);
            maxSum = Math.max(maxSum, sumCol[i]);
        } 
        
        int count = 0;
        for (int i = 0, j = 0; i < n && j < n;) 
        {
            //finding minimum increment required in either row or column.
            int diff = Math.min(maxSum - sumRow[i], maxSum - sumCol[j]);
            
            //adding difference in corresponding cell, 
            //sumRow[] and sumCol[] array.
            matrix[i][j] += diff;
            sumRow[i] += diff;
            sumCol[j] += diff;
            
            //updating the result.
            count += diff;
            
            //if ith row is satisfied, incrementing i for next iteration.
            if (sumRow[i] == maxSum)
                ++i;
            
            //if jth column is satisfied, incrementing j for next iteration.
            if (sumCol[j] == maxSum)
                ++j;
        }
        //returning the result.
        return count;
    }
}
class Solution
{
    //Function to modify the matrix such that if a matrix cell matrix[i][j]
    //is 1 then all the cells in its ith row and jth column will become 1.
    void booleanMatrix(int matrix[][])
    {
        int r = matrix.length;
        int c = matrix[0].length;

        //using two list to keep track of the rows and columns 
        //that needs to be updated with 1.
        int row[] = new int[r];
        int col[] = new int[c];
        
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                //if we get 1 in matrix, we mark ith row and jth column as 1.
                if(matrix[i][j] == 1){
                    row[i] = 1;
                    col[j] = 1;
                }  
            }
        }
        
        for(int i =0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                //if ith row or jth column is marked as 1, then all elements
                //of matrix in that row and column will be 1.
                if(row[i] == 1 || col[j] == 1){
                    matrix[i][j] = 1;
                }
            }
        }
    }
}
class Solution
{
    //Function to interchange the rows of a matrix.
    static void interchangeRows(int matrix[][])
    {
       for(int i=0;i<matrix.length/2;i++){
           for(int j=0;j<matrix[i].length;j++){
               int temp=matrix[i][j];
               matrix[i][j]=matrix[matrix.length-i-1][j];
               matrix[matrix.length-i-1][j]=temp;
           }
       } 
    }
}
class Solution
{
    //Function to reverse the columns of a matrix.
    static void reverseCol(int matrix[][])
    {
       for(int i=0; i<matrix.length; i++){
           for(int j=0; j<matrix[i].length/2; j++)
           {
               int temp = matrix[i][j];
               matrix[i][j] = matrix[i][matrix[i].length-j-1];
               matrix[i][matrix[i].length-j-1] = temp;
           }
       } 
    }
}
class Solution
{
    //Function to exchange first column of a matrix with its last column.
    static void exchangeColumns(int matrix[][])
    {
       int temp = 0;
       for (int i=0; i<matrix.length; i++)
       {
            temp = matrix[i][0];
            matrix[i][0] = matrix[i][matrix[i].length-1];
            matrix[i][matrix[i].length-1] = temp; 
       }
    }
}
class Solution
{
    //Function to get cofactor of matrix[p][q] in temp[][]. 
    static void getCofactor(int matrix[][], int temp[][], int p, int q, int n)
    {
        int i = 0, j = 0;

        for (int row = 0; row < n; row++)
        {
            for (int col = 0; col < n; col++)
            {
                //copying only those elements into temporary matrix 
                //which are not in given row and column.
                if(row != p && col != q)
                {
                    temp[i][j++] = matrix[row][col];

                    //if row is filled, we increase row index and
                    //reset column index.
                    if(j == n - 1)
                    {
                        j = 0;
                        i++;
                    }
                }
            }
         }
    }
    
    
    //Function for finding determinant of matrix.
    static int determinantOfMatrix(int matrix[][], int n)
    {
        int D = 0; 

        //base case
        if (n == 1)
            return matrix[0][0];

        //creating a list to store Cofactors.
        int temp[][]  = new int[n][n];

        int sign = 1;

        //iterating for each element of first row.
        for (int i = 0; i < n; i++)
        {
            //getting Cofactor of matrix[0][i].
            getCofactor(matrix, temp, 0, i, n);
            D += sign * matrix[0][i] * determinantOfMatrix(temp, n - 1);

            //terms are to be added with alternate sign so changing the sign.
            sign = -sign;
        }
        //returning the determinant.
        return D;
    }
}
class Solution
{
    //Function to multiply two matrices.
    static int[][] multiplyMatrix(int A[][], int B[][])
    {
        int n1 = a.length;
        int m1 = a[0].length;
        int n2 = b.length;
        int m2 = b[0].length;
        
        if(m1!=n2)
        {
            int arr0[][] = new int[1][1];
            arr0[0][0] = -1;
            return arr0;
        }
        
        int arr[][] = new int[n1][m2];
        
        for(int i = 0 ; i<n1 ; i++)
        for(int j = 0 ; j<m2 ; j++)
        for(int q = 0; q<n2 ; q++)
        arr[i][j]+= a[i][q]*b[q][j];
        
        return arr;
    }
}
class Solution
{
    //Function to return sum of upper and lower triangles of a matrix.
    static ArrayList<Integer> sumTriangles(int matrix[][], int n)
    {
        ArrayList<Integer> list=new ArrayList<>();
        int sum1=0;
        int sum2=0;
        for(int g=0; g<matrix.length; g++){
            for(int i=0, j=g; j<matrix.length; i++,j++){
                sum1+=matrix[i][j];
            }
        }
        list.add(sum1);
        for(int g=0; g<matrix.length; g++){
            for(int i=g,j=0; i<matrix.length; i++,j++){
                sum2+=matrix[i][j];
            }
        }
        list.add(sum2);
        return list;
    }
}
class Solution
{
    //Function to add two matrices.
    static int[][] sumMatrix(int A[][], int B[][])
    {
        int n = A.length, m = A[0].length;
        int res[][] = new int[0][0];
        //Check if two input matrix are of different dimensions
        if(n != B.length || m != B[0].length)
            return res;
        
        res = new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                res[i][j] = A[i][j] + B[i][j];
                
        return res;
    }
}
// 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);
    } 
}
class Solution
{
  //Function to find median of the array elements.  
  public int median(int A[],int N)
    {
      
        Arrays.sort(A);
        int k=N/2;
        if(N%2!=0){
            return A[k];
        }
        else{
            return (A[k-1]+A[k])/2;
        }
    }
    //Function to find median of the array elements.
    public int mean(int A[],int N)
    {
        int sum=0;
        for(int i=0;i<N;i++)
        {
            sum=sum+A[i];
        }
        return sum/N;
    }

}
class Solution {
    // Function to find element with more appearances between two elements in an
    // array.
    public int majorityWins(int arr[], int n, int x, int y) 
    {
        int countX=0;
        int countY=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==x)
                countX++; 
             
             if(arr[i]==y)
                 countY++;
         }
         
        if(countX>countY)
            return x;
         
        else if(countX==countY && x<y)
            return x;
         
        else 
            return y;
    }
}
class Solution{
    
    // Function to find largest and second largest element in the array
    public static ArrayList<Integer> largestAndSecondLargest(int sizeOfArray, int arr[])
       {
           //code here.
           int largest=-1;
           int sec_largest=-1;
           for(int i=0;i<sizeOfArray;i++)
           {
               largest = Math.max(largest,arr[i]);
           }
           for(int i=0;i<sizeOfArray;i++)
           {
               if(arr[i]<largest)
               {
                   sec_largest= Math.max(sec_largest,arr[i]);
               }
           }
           ArrayList<Integer> al = new ArrayList<Integer>(2);
           al.add(largest);
           al.add(sec_largest);
           return al;
       }
    }
}
class StrongestNeighbour{
    
    // Function to find maximum for every adjacent pairs in the array.
    static void maximumAdjacent(int sizeOfArray, int arr[])
    {
        int sum=0;
        for(int i=0; i<sizeOfArray-1; i++)
        {
            sum = Math.max(arr[i], arr[i+1]);  
            System.out.print(sum+" ");
            
        }
    }
}
class Solution{
    //Function to reverse any part of the array.
    void reverse(ArrayList<Integer> arr, int n,int left, int right)
    {
           //reversing the sub-array from left index to right index.
            while (left < right) { 
                //swapping values at index stored at left and right index.
                int temp = arr.get(left); 
                arr.set(left, arr.get(right)); 
                arr.set(right, temp);
                
                //updating values of left and right index.
                left+=1; 
                right-=1;  
            }
    }
    
    //Function to reverse every sub-array group of size k.
    void reverseInGroups(ArrayList<Integer> arr, int n, int k) {
        for (int i = 0; i < n; i += k) { 
            
            //If (ith index +k) is less than total number of elements it means
            //k elements exist from current index so we reverse k elements 
            //starting from current index.
            if(i+k < n){ 
                //reverse function called to reverse any part of the array.
                reverse(arr,n,i,i+k-1);
            }
            //Else k elements from current index doesn't exist. 
            //In that case we just reverse the remaining elements.
            else{
                //reverse function called to reverse any part of the array.
                reverse(arr,n,i,n-1);
            }
           
        }
    }
}
class Solution{
    
    //Function to find minimum adjacent difference in a circular array.
    // arr[]: input array
    // n: size of array
    public static int minAdjDiff(int arr[], int n) {
    
       int min=Math.abs(arr[0]-arr[n-1]),diff;
        for(int i=0;i<n-1;i++)
        {
            diff=Math.abs(arr[i]-arr[i+1]);
            if(diff<min)
            min=diff;
        }
        return min;
       
    }
}
class Solution{

    //Function to swap two elements in the array.    
    public static void swap(int arr[], int x, int y){
        //Use of a temporary variable to swap the elements.
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
    //Function to sort the array into a wave-like array.
    public static void convertToWave(int arr[], int n){
        
        //Iterating over the array. 
        for(int i=0;i<n-1;i=i+2){
            //Swapping two neighbouring elements at a time.
		    swap(arr, i, i+1);
		}
        return;
    }
    
}
class Solution{
    //Function to count the frequency of all elements from 1 to N in the array.
    public static void frequencyCount(int arr[], int N, int P)
    {
        //Decreasing all elements by 1 so that the elements
        //become in range from 0 to n-1.
        int maxi = Math.max(P,N);
        int count[] = new int[maxi+1];
        Arrays.fill(count, 0);
        for(int i=0;i<N;i++){
            count[arr[i]]++; 
        }
        
        for(int i=0;i<N;i++){
            arr[i] = count[i+1];
        }
    }
}
class Solution {
    // Function to find equilibrium point in the array.
    public static int equilibriumPoint(long a[], int n) {

        //We store the sum of all array elements.
        long sum = 0;
        for (int i = 0; i < n; i++) 
           sum += a[i];

        //sum2 is used to store prefix sum.
        long sum2 = 0;
        int ans = -1;

        for (int i = 0; i < n; i++) {
            
            //Leaving out the value of current element from suffix sum.
            sum = sum - a[i];
            
            //Checking if suffix and prefix sums are same.
            if (sum2 == sum) {
                //returning the index or equilibrium point.
                return (i + 1);
            }
            
            //Adding the value of current element to prefix sum.
            sum2 = sum2 + a[i];
        }
        return -1;
    }
}
class Solution{
    //Function to find the leaders in the array.
    static ArrayList<Integer> leaders(int arr[], int n){
        
        int maxEle = arr[n-1];
        
        ArrayList<Integer> res = new ArrayList<>();
        
        //We start traversing the array from last element.
        for(int i=n-1; i>=0; i--) {
            
            //Comparing the current element with the maximum element stored. 
            //If current element is greater than max, we add the element.
		    if(arr[i] >= maxEle){
		        //Updating the maximum element.
		        maxEle = arr[i];
		        //Storing the current element in arraylist for leaders.
		        res.add(maxEle);
		    }
		}
		
		//Reversing the arraylist.
		Collections.reverse(res);
		//returning the arraylist.
        return res;
    }
    
}
class Solution
{
    //Function that puts all non-positive (0 and negative) numbers on left 
    //side of arr[] and return count of such numbers.
    static int segregate (int arr[], int size)
    {
        int j = 0, i;
        for(i = 0; i < size; i++)
        {
           if (arr[i] <= 0)  
           {
               int temp;
               //changing the position of negative numbers and 0.
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               //incrementing count of non-positive integers.
               j++;  
           }
        } 
        return j;
    }
    
    //Finding the smallest positive missing number in an array 
    //that contains only positive integers.
    static int findMissingPositive(int arr[], int size)
    {
        int i;
        //marking arr[i] as visited by making arr[arr[i] - 1] negative. 
        //note that 1 is subtracted because indexing starts from 0 and 
        //positive numbers start from 1.
        for(i = 0; i < size; i++)
        {
            if(Math.abs(arr[i]) - 1 < size && arr[Math.abs(arr[i]) - 1] > 0)
            arr[Math.abs(arr[i]) - 1] = -arr[Math.abs(arr[i]) - 1];
        }
        
        for(i = 0; i < size; i++)
        {
            if (arr[i] > 0)
            {
                //returning the first index where value is positive.
                // 1 is added because indexing starts from 0.
                return i+1;
            }
        }
        return size+1;
    }
    
    //Function to find the smallest positive number missing from the array.
    static int missingNumber(int arr[], int size)
    {
        //first separating positive and negative numbers. 
        int shift = segregate (arr, size);
        
        int arr2[] = new int[size-shift];
        int j=0;
        //shifting the array to access only positive part.
        for(int i=shift;i<(size);i++)
        {
            arr2[j] = arr[i];
            j++;
        }
        
        //calling function to find result and returning it.
        return findMissingPositive(arr2, j);
    }
    
}
class Solution{

    //Function to rearrange  the array elements alternately.
    public static void rearrange(long arr[], int n)
    {
        //Initialising index of first minimum and first maximum element. 
    	int max_idx = n - 1, min_idx = 0; 
    
    	 //Storing maximum element of array.
    	long max_elem = arr[n - 1] + 1; 
    
    	for (int i = 0; i < n; i++) { 
    	    
    		//At even index, we have to put maximum elements in decreasing order. 
    		if (i % 2 == 0) { 
    			arr[i] += (arr[max_idx] % max_elem) * max_elem; 
    			//Updating maximum index.
    			max_idx--; 
    		} 
    
    		//At odd index, we have to put minimum elements in increasing order. 
    		else { 
    			arr[i] += (arr[min_idx] % max_elem) * max_elem; 
    			//Updating minimum index.
    			min_idx++; 
    		} 
    	} 
    
    	//Dividing array elements by maximum element to get the result. 
    	for (int i = 0; i < n; i++) 
    		arr[i] = arr[i] / max_elem;
        
    }
    
}
class Solution
{
    //Function to rearrange an array so that arr[i] becomes arr[arr[i]]
    //with O(1) extra space. 
    static void arrange(long arr[], int n)
    {
        int i = 0;
        
        //Increasing all values by (arr[arr[i]]%n)*n to store the new element.
        for(i = 0; i < n; i++)
         arr[(int)i]+=(arr[(int)arr[(int)i]]%n)*n;
        
        //Since we had multiplied each element with n.
        //We will divide by n too to get the new element at that 
        //position after rearranging.
        for(i = 0; i < n; i++)
            arr[(int)i] = arr[(int)i]/n;
    }
}
class Solution{
    // Function to find the maximum index difference.
    static int maxIndexDiff(int arr[], int n) { 
        if(n==1){
            return 0;
        }
        int RMax[] = new int[n]; 
        int LMin[] = new int[n]; 
        
        //Constructing LMin[] such that LMin[i] stores the minimum value 
        //from (arr[0], arr[1], ... arr[i]).
        LMin[0] = arr[0];
        for (int i = 1; i < n; ++i) 
            LMin[i] = Integer.min(arr[i], LMin[i - 1]);
            
        //Constructing RMax[] such that RMax[j] stores the maximum value 
        //from (arr[j], arr[j+1], ..arr[n-1]). 
        RMax[n - 1] = arr[n - 1]; 
        for (int j = n - 2; j >= 0; --j)
            RMax[j] = Integer.max(arr[j], RMax[j + 1]); 
            
        int i = 0, j = 0, maxDiff = -1; 
        //Traversing both arrays from left to right to find optimum j-i.
        //This process is similar to merge() of MergeSort.
        while (j < n && i < n) { 
            if (LMin[i] <= RMax[j]) { 
                //Updating the maximum difference.
                maxDiff = Integer.max(maxDiff, j - i); 
                j++; 
            } else
                i++;
        }
        //returning the maximum difference.
        return maxDiff; 
    }
}
class Interval {
    int buy;
    int sell;
}

class Solution{
    //Function to find the days of buying and selling stock for max profit.
    ArrayList<ArrayList<Integer> > stockBuySell(int A[], int n) {
        
        ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
      //Prices must be given for at least two days else return the empty result.
        if(n==1){
            return result;
        }
        
        //Creating solution vector.
        ArrayList<Interval> sol = new ArrayList<Interval>();
        int i=0, cnt=0;
        //Traversing through given price array.
        while (i < n-1) {
            //Finding Local Minima. Note that the limit of loop is (n-2)
            //as we are comparing present element to the next element.
            while ((i < n-1) && (A[i+1] <= A[i])){
                i++;
            }
            //If we reach the end, we break loop as no further 
            //solution is possible.
            if (i == n-1){
                break;
            }
            Interval e = new Interval();
            //Storing the index of minima which gives the day of buying stock.
            e.buy = i++;
 
            //Finding Local Maxima. Note that the limit of loop is (n-1)
            //as we are comparing present element to previous element.
            while ((i < n) && (A[i] >= A[i-1]))
                i++;
 
            //Storing the index of maxima which gives the day of selling stock.
            e.sell = i-1;
            sol.add(e);
            //Incrementing count of buy/sell pairs.
            cnt++;
        }
        if(cnt==0){
            return result;
        } else {
            //Storing the buy/sell pairs in a list.
            for(int j=0; j<sol.size(); j++){
                result.add(new ArrayList<Integer>()); 
                result.get(j).add(0, sol.get(j).buy);
                result.get(j).add(1, sol.get(j).sell);
            }
        }
        //returning the result.
        return result;
    } 
    
}
import java.io.*;

class GFG {

	// Function to check if an array is
	// Sorted and rotated clockwise
	static boolean checkIfSortRotated(int arr[], int n)
	{
		// Initializing two variables x,y as zero.
		int x = 0, y = 0;

		// Traversing array 0 to last element.
		// n-1 is taken as we used i+1.
		for (int i = 0; i < n - 1; i++) {
			if (arr[i] < arr[i + 1])
				x++;
			else
				y++;
		}

		// If till now both x,y are greater
		// then 1 means array is not sorted.
		// If both any of x,y is zero means
		// array is not rotated.
		if (x == 1 || y == 1) {
			// Checking for last element with first.
			if (arr[n - 1] < arr[0])
				x++;
			else
				y++;

			// Checking for final result.
			if (x == 1 || y == 1)
				return true;
		}
		// If still not true then definitely false.
		return false;
	}

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

		int n = arr.length;

		// Function Call
		boolean x = checkIfSortRotated(arr, n);
		if (x == true)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}
1.) Maximum subarray size, such that all subarrays of that size have sum less than k: 
-------------------------------------------------------------------------------------
    Given an array of n positive integers and a positive integer k, the task is to find the maximum 	subarray size such that all subarrays of that size have the sum of elements less than k.

    https://www.geeksforgeeks.org/maximum-subarray-size-subarrays-size-sum-less-k/

2.) Find the prime numbers which can written as sum of most consecutive primes: 
-------------------------------------------------------------------------------
    Given an array of limits. For every limit, find the prime number which can be written as the 	 sum of the most consecutive primes smaller than or equal to the limit.
    
    https://www.geeksforgeeks.org/find-prime-number-can-written-sum-consecutive-primes/

3.) Longest Span with same Sum in two Binary arrays : 
-----------------------------------------------------
    Given two binary arrays, arr1[] and arr2[] of the same size n. Find the length of the longest       common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] +           arr2[i+1] + …. + arr2[j].
    
    https://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/

3.) Maximum subarray sum modulo m: 
----------------------------------
    Given an array of n elements and an integer m. The task is to find the maximum value of the sum 	of its subarray modulo m i.e find the sum of each subarray mod m and print the maximum value of 	this modulo operation.
    
    https://www.geeksforgeeks.org/maximum-subarray-sum-modulo-m/

4.) Maximum subarray size, such that all subarrays of that size have sum less than k: 
-------------------------------------------------------------------------------------
	Given an array of n positive integers and a positive integer k, the task is to find the maximum 	subarray size such that all subarrays of that size have sum of elements less than k.
    
    https://www.geeksforgeeks.org/maximum-subarray-size-subarrays-size-sum-less-k/

5.) Minimum cost for acquiring all coins with k extra coins allowed with every coin: 
---------------------------------------------------------------------------------
	You are given a list of N coins of different denominations. you can pay an amount equivalent to 	any 1 coin and can acquire that coin. In addition, once you have paid for a coin, we can choose 	at most K more coins and can acquire those for free. The task is to find the minimum amount 	required to acquire all the N coins for a given value of K.

    https://www.geeksforgeeks.org/minimum-cost-for-acquiring-all-coins-with-k-extra-coins-allowed-with-every-coin/
    
6.) Random number generator in arbitrary probability distribution fashion: 
----------------------------------------------------------------------
	Given n numbers, each with some frequency of occurrence. Return a random number with a 			probability proportional to its frequency of occurrence.
    
    https://www.geeksforgeeks.org/random-number-generator-in-arbitrary-probability-distribution-fashion/
// 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);
    } 
}
What you will learn :

 - All important concepts of Data Structures & Algorithms

 - How to enhance your problem solving skills for the product-based companies

 - Extensive knowledge on algorithms & frequently asked questions to help better your coding skills

 - Learn the problem-solving approach for the puzzle based questions asked in interviews
class Solution
{
    // String array to store keypad characters
    static String hash[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    //Function to find list of all words possible by pressing given numbers.
    static ArrayList <String> possibleWords(int a[], int N)
    {
        String str = "";
        for(int i = 0; i < N; i++)
        str += a[i];
        ArrayList<String> res = possibleWordsUtil(str);
        //arranging all possible strings lexicographically.
        Collections.sort(res); 
        return res;
                    
    }
    
    //recursive function to return all possible words that can
    //be obtained by pressing input numbers.  
    static ArrayList<String> possibleWordsUtil(String str)
    {
        //if str is empty 
        if (str.length() == 0) { 
            ArrayList<String> baseRes = new ArrayList<>(); 
            baseRes.add(""); 
  
            //returning a list containing empty string.
            return baseRes; 
        } 
        
        //storing first character of str
        char ch = str.charAt(0); 
        //storing rest of the characters of str 
        String restStr = str.substring(1); 
  
        //getting all the combination by calling function recursively.
        ArrayList<String> prevRes = possibleWordsUtil(restStr); 
        ArrayList<String> Res = new ArrayList<>(); 
      
        String code = hash[ch - '0']; 
  
        for (String val : prevRes) { 
  
            for (int i = 0; i < code.length(); i++) { 
                Res.add(code.charAt(i) + val); 
            } 
        } 
        //returning the list.
        return Res; 
    }
}
class LexSort
{
    static void solve(String s,String out, ArrayList<String> ans ,int i){
        if(i==s.length()){
            ans.add(out);
            return;
        }
        char ch=s.charAt(i);
        solve(s,out,ans,i+1);
        solve(s,out+String.valueOf(ch),ans,i+1);
    }
    
    //Function to return the lexicographically sorted power-set of the string.
    static ArrayList<String> powerSet(String s)
    {
        ArrayList<String> ans= new ArrayList<>();
        solve(s,"",ans,0);
        return ans;
    }
}
class Solution
{
    public long modfun(long n, long  R)
    {
        // Base cases 
        if (n == 0) 
            return 0; 
        // power zero mean answer is 1
        if (R == 0)  
            return 1; 
        // If R is even 
        long y; 
        if (R % 2 == 0) { 
            // finding r/2 power as power is even then storing answer in y and if power is even like 2^4 we can simply do (2^2)*(2^2)
            y = modfun(n, R/2);  
            y = (y * y) % 1000000007; 
        } 
      
        // If R is odd 
        else { 
            y = n % 1000000007; 
            // reduce the power by 1 to make it even. The reducing power by one can be done if we take one n out. Like 2^3 can be written as 2*(2^2)
            y = (y * modfun(n, R - 1) % 1000000007) % 1000000007; 
        } 
        // finally return the answer (y+mod)%mod = (y%mod+mod%mod)%mod = (y%mod)%mod
        return ((y + 1000000007) % 1000000007);  
        }
        
        
    long power(int N,int R)
    {
        return modfun(N,R)%1000000007;
        
    }

}
class Solution
{
    static int RecursivePower(int n, int p)
    {
       if(p==0){
           return 1;
       }
       return n*RecursivePower(n, p-1);
    }
}
class Solution
{
    public static boolean check(int n,int counter)
    {
        if(counter<=n){
            if(n%counter==0)
                return false;
		    // calculate next position of input number
		    n=n-n/counter;
		    counter++;
		    // make recursive call with updated counter 
		    // and position return check(n, counter);
		    return check(n, counter);
        }    
       	else
       		return true;
    }
    
    // n: Input n
    // Return True if the given number is a lucky number else return False
    public static boolean isLucky(int n)
    {
        return check(n,2);
    }
}
class Solution
{
    public static int digitalRoot(int n)
    {
        if(n < 10)
            return n;

        return digitalRoot(n%10 + n/10);
    }
}
class Solution
{
    public static int countDigits(int n)
    {
        if(n<10)
            return 1;
        else
            // recursively count the digits of n
            return 1+countDigits(n/10);
    }
}
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));

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

class Solution
{
    
  public int modInverse(int a, int m)
    {
        for(int i=1; i<m; i++){
            if(a*i%m == 1)
                return i;
        }
        return -1;
    }
}

class Main {
	public static void main (String[] args) {
	    
	    //taking input using Scanner class
		Scanner sc=new Scanner(System.in);
		
		//taking testcases
		int T=sc.nextInt();
		
		while(T-->0)
		{
		    Solution  obj=new Solution ();
		    int a,m;
		      
            //taking input a and m
		    a=sc.nextInt();
		    m=sc.nextInt();
		  
            //calling function modInverse()
		    System.out.println(obj.modInverse(a,m));
		}
		
	}
}
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution
{
    static long multiplicationUnderModulo(long a, long b)
    {
        long M = 1000000007;
        return ((a%M)*(b%M))%M;
    }
}

class GFG
{
    public static void main(String args[])throws IOException
    {
        
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        
        //taking testcases
        int t = Integer.parseInt(read.readLine());
        
        while(t-- > 0)
        {
            String str[] = read.readLine().trim().split(" ");
            
            //taking input a and b
            long a = Long.parseLong(str[0]);
            long b = Long.parseLong(str[1]);

            //calling multiplicationUnderModulo() function
            System.out.println(new Solution().multiplicationUnderModulo(a, b));
        }
    }
}
import java.io.*;
import java.util.*;

class Solution
{
    public static boolean isPrime(int num)
    {
        if(num==1) return false;
        if(num==2 || num==3) return true;
        if(num%2==0 || num%3==0) return false;
        for(int i=5; i*i<=num; i+=6)
        {
            if(num%i==0 || num%(i+2)==0)
                return false;
        }
        return true;
    }

    public static int exactly3Divisors(int N)
    {
        int count = 0;
        for(int i=2; i*i<=N; i++)
        {
            if(isPrime(i))
                count++;
        }
        return count;
    }
}

class Main {
	public static void main (String[] args) {
		Scanner sc=new Scanner(System.in);

		//taking testcases
		int T=sc.nextInt();
		
		while(T-->0)
		{
		    Solution obj=new Solution();
		    int N;
		    N=sc.nextInt();//taking N
		    //calling function exactly3Divisors()
		    System.out.println(obj.exactly3Divisors(N));
		}
		
	}
}
import java.io.*;
import java.util.*;

class Solution
{
    
    public double termOfGP(int A,int B,int N)
    {
        // common ratio is given by r=b/a
        double r=(double)B/(double)A;
        // Nth term is given by a(r^(N-1))
        return (A*Math.pow(r,N-1)); 
    }

}

public class Main {
	public static void main (String[] args) {
	    
	    //taking input using Scanner class
		Scanner sc=new Scanner(System.in);
		
		//taking total testcases
		int T=sc.nextInt();
		while(T-->0)
		{
		    
		    Solution  obj=new Solution ();
		    int A,B;
		    
		    //taking A and B
		    A=sc.nextInt();
		    B=sc.nextInt();
		    int N;
		    
		    //taking N
		    N=sc.nextInt();
		    
		   //calling method termOfGP() of class GP
		   System.out.println((int)Math.floor(obj.termOfGP(A,B,N)));
		    
		}
		
	}
}
import java.io.*;
import java.util.*;

class Solution{
    public int digitsInFactorial(int N){
        
        if (N < 0)
            return 0;
  
        // base case
        if (N <= 1)
            return 1;
  
        // else iterate through n and calculate the value
        double digits = 0;
        for (int i=2; i<=N; i++)
            digits += Math.log10(i);
  
        return (int)(Math.floor(digits)) + 1;
    }
}

public class Main {
	public static void main (String[] args) {
		Scanner sc=new Scanner(System.in);
		
		//taking total testcases
		int T=sc.nextInt();
		
		while(T-->0)
		{
		    Solution obj=new Solution();
		    int N;
		    
		    //taking N
		    N=sc.nextInt();
		    
		   //calling method digitsInFactorial()
		   System.out.println(obj.digitsInFactorial(N));
		    
		}
		
	}
}
import java.io.*;
import java.util.*;

class Solution {
    public ArrayList<Integer> quadraticRoots(int a, int b, int c) {
        
       ArrayList<Integer> numbers = new ArrayList<Integer>();
       int d = (int) (Math.pow(b,2)-(4*a*c));
       int r1 = (int) Math.floor(((-1*b)+Math.sqrt(d))/(2*a));
       int r2 = (int) Math.floor(((-1*b)-Math.sqrt(d))/(2*a));
       if(d<0){
           numbers.add(-1);
       }
       else
       {
           numbers.add(Math.max(r1,r2));
           numbers.add(Math.min(r1,r2));
       }
       return numbers;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            Solution obj = new Solution();
            ArrayList<Integer> ans = obj.quadraticRoots(a, b, c);
            if (ans.size() == 1 && ans.get(0) == -1)
                System.out.print("Imaginary");
            else
                for (Integer val : ans) System.out.print(val + " ");
            System.out.println();
        }
    }
}
// Formula	: (0°C × 9/5) + 32 = 32°F

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

class Solution
{
    public double cToF(int C)
    {
        return C*(9.0/5.0)+32.0;
    }
}

public class Main {
	public static void main (String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int T=sc.nextInt();//input number of testcases
		while(T-->0)
		{
		    Solution obj=new Solution();
		    
		    int C;
		    C=sc.nextInt();//input temperature in celscius
		    
		    System.out.println((int)(obj.cToF(C)));//print the output
		}
		
	}
}
import java.util.*;
import java.io.*;

class Solution {
    public static long sumUnderModulo(long a, long b){
        
        long M = 1000000007;
        // a+b mod M = (a mod M + b mod M)mod M
        return  (a % M + b % M)%M;
    }   
}

class GFG
{
    public static void main(String args[])throws IOException
    {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        
        //taking testcases
        int t = Integer.parseInt(read.readLine());
        
        while(t-- > 0) {
            String[] str = read.readLine().trim().split(" ");
            
            //taking input a and b
            Long a = Long.parseLong(str[0]);
            Long b = Long.parseLong(str[1]);
            
            //calling method sumUnderModulo()
            System.out.println(new Solution().sumUnderModulo(a,b));
        }
    }
}
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt(); // number of testcases
        while (T > 0) {
            int I = sc.nextInt();
            Solution obj = new Solution();
            System.out.println(obj.absolute(I));

            T--;
        }
    }
}


class Solution {
    public int absolute(int I) {
       int absolute=Math.abs(I);
       return absolute;
       
       /*
       //used a simple logic 

       if(I<0){
           I=-I;
       }
       else if(I==0){
          I=0;
       }
       else{
           I=I;
       }
       return I;
       */
    }
}
star

Tue Feb 08 2022 15:37:30 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #heap #priorityqueue
star

Tue Feb 08 2022 15:33:09 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #heap #heapsort
star

Tue Feb 08 2022 15:31:09 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #heap #binaryheap #buildheap
star

Tue Feb 08 2022 15:21:53 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #heap #binaryheap #heapinsert
star

Tue Feb 08 2022 15:19:35 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #heap #binaryheap
star

Tue Feb 08 2022 15:08:17 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #sorting #mergesort
star

Tue Feb 08 2022 15:00:15 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #sorting #merge #sortedarrays
star

Tue Feb 08 2022 14:56:44 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #sorting #insertionsort
star

Tue Feb 08 2022 14:54:48 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #sorting #selectionsort
star

Tue Feb 08 2022 14:45:51 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #sorting #bubblesort
star

Tue Feb 08 2022 14:37:36 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #searching #allocate #minimumpages
star

Tue Feb 08 2022 14:28:19 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #searching #repeatingelements
star

Tue Feb 08 2022 13:59:55 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #searching #peakelement
star

Tue Feb 08 2022 13:47:36 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #searching #infinitearray
star

Tue Feb 08 2022 13:42:51 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #searching #squareroot
star

Tue Feb 08 2022 12:38:20 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #string #lexicographicrank
star

Tue Feb 08 2022 12:29:55 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #string #anagramsearch
star

Tue Feb 08 2022 12:11:58 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #string #rotations
star

Tue Feb 08 2022 11:12:51 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #string #reversewords
star

Tue Feb 08 2022 10:39:34 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #string #anagram
star

Tue Feb 08 2022 10:19:51 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #string #palindrome
star

Tue Feb 08 2022 09:38:53 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/make-matrix-beautiful-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #beautifulmatrix
star

Tue Feb 08 2022 09:35:30 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/boolean-matrix-problem-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #booleanmatrix
star

Tue Feb 08 2022 09:32:41 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/reversing-the-rows-of-a-matrix-1587115621/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #interchangingrows
star

Tue Feb 08 2022 08:47:50 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/reversing-the-columns-of-a-matrix-1587115621/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #reversingcolumns
star

Tue Feb 08 2022 08:41:01 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/exchange-matrix-columns-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #exchangecolumns
star

Tue Feb 08 2022 08:29:37 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/determinant-of-a-matrix-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #determinant
star

Tue Feb 08 2022 08:21:15 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/multiply-the-matrices-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #multiplication
star

Tue Feb 08 2022 08:14:36 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/sum-of-upper-and-lower-triangles-1587115621/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #sum
star

Tue Feb 08 2022 08:09:29 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/adding-two-matrices3512/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #addition #practice
star

Tue Feb 08 2022 07:29:55 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #transpose
star

Tue Feb 08 2022 06:38:10 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/mean-and-median-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #mean #median
star

Tue Feb 08 2022 06:33:11 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/who-has-the-majority/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #majority
star

Tue Feb 08 2022 06:26:48 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/max-and-second-max/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #max #secondmax
star

Tue Feb 08 2022 06:22:48 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/strongest-neighbour/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #strongestneighbour
star

Tue Feb 08 2022 06:17:15 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #arrays #practice #reversearray
star

Tue Feb 08 2022 06:10:45 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/minimum-absloute-difference-between-adjacent-elements-in-a-circular-array-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #circulararray #adjacentdifference #minimumadjacentdifference
star

Tue Feb 08 2022 05:46:24 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/wave-array-1587115621/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #wavearray
star

Tue Feb 08 2022 05:43:55 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/frequency-of-array-elements-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #frequencycount #frequencies #limitedrange
star

Tue Feb 08 2022 05:40:29 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/equilibrium-point-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #equilibriumpoint
star

Tue Feb 08 2022 05:35:58 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/leaders-in-an-array-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #leaders
star

Tue Feb 08 2022 05:32:27 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/smallest-positive-missing-number-1587115621/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #smallestpositive #missingnumber
star

Tue Feb 08 2022 05:22:26 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #rearrange #alternately
star

Tue Feb 08 2022 05:08:33 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/rearrange-an-array-with-o1-extra-space3142/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #rearrange
star

Tue Feb 08 2022 05:04:45 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/maximum-index-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #practice #maximumindex #maximumdifference
star

Tue Feb 08 2022 04:43:41 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/stock-buy-and-sell-1587115621/1/?track=DSASP-Arrays&batchId=190#

#java #gfg #geeksforgeeks #arrays #stock #practice #buysell #stockbuysell
star

Tue Feb 08 2022 04:33:48 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/check-if-array-is-sorted-and-rotated-clockwise-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #arrays #sorted #rotated
star

Mon Feb 07 2022 15:51:57 GMT+0000 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) https://www.geeksforgeeks.org/maximum-occurred-integer-n-ranges/

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

Mon Feb 07 2022 14:28:06 GMT+0000 (Coordinated Universal Time)

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

Mon Feb 07 2022 13:22:24 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #arrays #majorityelement
star

Mon Feb 07 2022 13:18:10 GMT+0000 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 23:52:07 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/batch/gcl-3

#java #gfg #geeksforgeeks #dsa #datastructures
star

Sun Feb 06 2022 23:42:45 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/possible-words-from-phone-digits-1587115620/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #possiblewordsfrom phone digits
star

Sun Feb 06 2022 23:27:01 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/power-set-using-recursion/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #powerset
star

Sun Feb 06 2022 23:19:49 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/power-of-numbers-1587115620/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #power #powerof numbers
star

Sun Feb 06 2022 23:13:54 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/power-using-recursion/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #powerusing recursion #power
star

Sun Feb 06 2022 23:08:00 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/lucky-numbers2911/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #luckynumbers
star

Sun Feb 06 2022 22:48:51 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/digital-root/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #digitalroot
star

Sun Feb 06 2022 22:43:14 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/count-total-digits-in-a-number/1/?track=DSASP-Recursion&batchId=190

#java #gfg #geeksforgeeks #recursion #countdigits
star

Sun Feb 06 2022 22:26:48 GMT+0000 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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:32:20 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #recursion #rope cutting
star

Sun Feb 06 2022 21:21:32 GMT+0000 (Coordinated Universal Time) 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:11:58 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #recursion #palindrome
star

Sun Feb 06 2022 21:09:41 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #recursion #naturalsum
star

Sun Feb 06 2022 21:03:20 GMT+0000 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) https://www.geeksforgeeks.org/program-count-digits-integer-3-different-methods/

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

Sun Feb 06 2022 02:13:52 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/modular-multiplicative-inverse-1587115620/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #modularmultiplicativeinverse
star

Sun Feb 06 2022 02:09:46 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/multiplication-under-modulo/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #multiplicationundermodulo
star

Sun Feb 06 2022 02:04:54 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/exactly-3-divisors/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #exactly3divisors
star

Sun Feb 06 2022 01:54:52 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/gp-term/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #gpterm #geometricprogressionterm #geometricseries
star

Sun Feb 06 2022 01:44:16 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/digits-in-factorial/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #digitsinfactorial
star

Sun Feb 06 2022 01:36:19 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/quadratic-equation-roots/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #quadraticequationroots
star

Sun Feb 06 2022 01:30:39 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/convert-celsius-to-fahrenheit/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #gfg #geeksforgeeks #convertcelsiustofahrenheit
star

Sat Feb 05 2022 12:20:21 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/addition-under-modulo/1/?track=DSASP-Mathematics&batchId=190

#java #additionundermodulo #mathematics #gfg #geeksforgeeks
star

Sat Feb 05 2022 12:16:24 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/absolute-value/1/?track=DSASP-Mathematics&batchId=190

#java #absolutevalue #mathematics #gfg #geeksforgeeks

Save snippets that work with our extensions

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