Posts

Showing posts from October, 2021

GFG Sorting Comparable and Comparator interface

  package com.company ; import java.awt. *; import java.util. *; import java.util. List ; class point { int x , y ; public point ( int x , int y ) { this . x = x ; this . y = y ; } } class myComparator implements Comparator < point >{ public int compare ( point p1 , point p2 ){ return p1 . x - p2 . x ; } } //Implementing Comparable interface //class point implements Comparable<point> { // int x, y; // public point(int x, int y) { // this.x = x; // this.y = y; // } // public int compareTo(point p){ // return x - p.x; // } //} //All even number comes first than all odd numbers class MyClass implements Comparator < Integer > { @Override public int compare ( Integer a , Integer b ) { return a % 2 - b % 2 ; } } public class Main { public static void main ( String [] args ) { // int[] array = {1,3,4,2,98,78}; //// Arrays.sort(array); // Arrays.sor...

Repeating element GFG

  package com.company ; public class RepeatingElement { // EFFICIENT SOLUTION public static int getRepeatedElement ( int [] arr ) { int n = arr . length ; boolean [] visited = new boolean [ n ]; for ( int i = 0 ; i < n ; i ++) { visited [ i ] = false ; } for ( int i = 0 ; i < n ; i ++) { if ( visited [ arr [ i ]]){ return arr [ i ]; } visited [ arr [ i ]] = true ; } return - 1 ; } // More efficient solution public static int get ( int [] arr ){ int n = arr . length ; int slow = arr [ 0 ] + 1 ; int fast = arr [ 0 ] + 1 ; do { slow = arr [ slow ] + 1 ; fast = arr [ arr [ fast ] + 1 ] + 1 ; } while ( slow != fast ); slow = arr [ 0 ] + 1 ; while ( slow != fast ) { slow = arr [ slow ] + 1 ; fast = arr [ fast ] + 1 ; } return slow - 1 ; } ...

Median of two sorted array GFG *******

  package com.company ; import java.util.Arrays ; public class MedianOfSortedArray { //Median of two sorted array public static double median ( int [] arr , int [] array ) { int n = arr . length ; int m = array . length ; int [] find = new int [ n + m ]; for ( int i = 0 ; i < n ; i ++) { find [ i ] = arr [ i ]; } for ( int i = 0 ; i < m ; i ++) { find [ i + n ] = array [ i ]; } Arrays . sort ( find ); int a = find . length ; if ( a % 2 == 0 ) { int sum = find [ a / 2 ] + find [ a / 2 - 1 ]; return sum / 2.0 ; } else return find [ a / 2 ]; } //Efficient solution public static double getMedian ( int [] arr1 , int [] arr2 ) { int n1 = arr1 . length ; int n2 = arr2 . length ; int low = 0 ; int high = n1 ; while ( low <= high ){ int i1 = ( low + high ) / 2 ; ...

Peak element GFG

  package com.company ; public class PeakElement { // Finding the peak element public static int peak ( int [] arr ){ int n = arr . length ; 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 ; } // Efficient solution public static int getPeakElement ( int [] arr ) { int n = arr . length ; 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 ])) {...

Searching an element in sorted and rotated array GFG

  package com.company ; public class SearchingInSortedAndRotatedArray { // search in a sorted and roted array public static int search ( int [] arr , int x ) { int n = arr . length ; int low = 0 ; int high = n - 1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( arr [ mid ] == x ) { return mid ; } if ( arr [ mid ] > arr [ low ]) { if ( arr [ low ] <= x && arr [ mid ] > x ) { high = mid - 1 ; } else low = mid + 1 ; } else { if ( arr [ high ] >= x && arr [ mid ] < x ) { low = mid + 1 ; } else high = mid - 1 ; } } return - 1 ; } public static void main ( String [] args ) { int [] array = { 10 , 20 , 40 , 60 , 5 , 8 }; System ...

Searching element in sorted infinite array GFG

  package com.company ; public class SearchingInInfiniteArray { public static int binarySearching ( int [] arr , int x , int l , int h ) { int n = arr . length ; int low = l ; int high = h ; while ( low <= high ) { int mid =( low + high ) / 2 ; if ( arr [ mid ] == x ){ return mid ; } else if ( arr [ mid ] < x ) { low = mid + 1 ; } else { high = mid - 1 ; } } return - 1 ; } // Searching an element in an infinite array // Recursive approach public static int search ( int [] arr , int x , int index ) { if ( arr [ index ] == x ) { return index ; } else if ( arr [ index + 1 ] > x && arr [ index ] < x ) { return - 1 ; } else { return search ( arr , x , index + 1 ); } } //Iterative approach public st...

Square root using Binary search concept GFG

  package com.company ; public class SquareRoot { // Finding the square root of a given number // 1. Naive solution public static int squareRoot ( int x ) { // return (int)Math.sqrt(x); int i = 0 ; while ( i * i <= x ) { i ++; } return i - 1 ; } // Efficient solution public static int getSquareRoot ( int n ) { int low = 1 ; int high = n ; int ans = - 1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; int sMid = mid * mid ; if ( sMid == n ) { return mid ; } else if ( sMid > n ) { high = mid - 1 ; } else { low = mid + 1 ; ans = mid ; } } return ans ; } public static void main ( String [] args ) { System . out . println ( getSquareRoot ( 10 )); } }

Count of 1 in a sorted binary array GFG

  package com.company ; public class Count1S { // Counting the number of 1 in binary sorted array public static int getCount ( int [] arr ) { int n = arr . length ; int first = countOccurrence . firstIndex ( arr , 1 ); if ( first == - 1 ) { return 0 ; } return ( n - first ) ; } public static void main ( String [] args ) { int [] array = { 0 , 0 , 0 , 1 , 1 , 1 , 1 }; System . out . println ( getCount ( array )); } }

Count occurrence GFG

  package com.company ; public class countOccurrence { // Number of times an element occur in an array // 1. Naive solution public static int getOccurrence ( int [] arr , int x ) { int n = arr . length ; int count = 0 ; for ( int i = 0 ; i < n ; i ++) { if ( arr [ i ] == x ) { count ++; } } return count ; } // 2. Efficient solution public static int firstIndex ( int [] arr , int x ) { int n = arr . length ; // Finding the index of first occurrence of an element int low = 0 ; int high = n - 1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( arr [ mid ] == x ) { if ( mid == 0 || arr [ mid ] != arr [ mid - 1 ]) { return mid ; } else high = mid - 1 ; } else if ( arr [ mid ] > x ) { high = mid - 1 ...