Question: Write a program to return minimum and maximum in an array. Your program should make the minimum number of comparisons.

Answer:
Logic:
 Iterative: ( O ^ n )
 Declare min and max ( min = 10000000 , max = 0 )
 iterate through every element in the array and check if it is greater than max OR lesser than min. and update accordingly
 Tournament method:( O ^ log2n )
 Declare min and max ( min = 10000000 , max = 0 )
 Run two loops. 1) From arr [ 0 ] to arr [ arr.length/2 ] . 2)From arr [ arr.length/2 ] to arr[ arr.length 1 ];
 and find max1 and min1 from the first loop and max2 and min2 from the second loop.
 Compare max1 and max2 AND min1 and min2
 Print the greater max and lower min
 Sorting method:( O ^ logn ):
 Sort the array ( here I have used inbuilt function but you can actually implement the sorting technique to solve)
 Print arr [ 0 ] as min and arr[ arr.length  1 ] as max
import java.util.*; public class Solution{ public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; for(int i=0; i<arr.length; i++){ arr[i] = sc.nextInt(); } int maxIterative = 0; int minIterative = 100000000; //This is Iterative method for(int i=0; i<arr.length; i++){ if(arr[i]>maxIterative){ maxIterative = arr[i]; } if(arr[i]<minIterative){ minIterative = arr[i]; } } System.out.println("Max by iterative is: "+maxIterative); System.out.println("Min by iterative is: "+minIterative); //This is Tournament method int maxTour1 = 0; int maxTour2 = 0; int minTour1 = 100000000; int minTour2 = 100000000; for(int i=0; i<arr.length/2; i++){ if(arr[i]>maxTour1){ maxTour1 = arr[i]; } if(arr[i]<minTour1){ minTour1 = arr[i]; } } for(int i=arr.length/2; i<arr.length; i++){ if(arr[i]>maxTour2){ maxTour2 = arr[i]; } if(arr[i]<minTour2){ minTour2 = arr[i]; } } if(maxTour1<maxTour3){ System.out.println("Max by Tournament method is: "+maxTour2); }else{ System.out.println("Max by Tournament method is: "+maxTour1); } if(minTour1<minTour2){ System.out.println("Min by Tournament method is: "+minTour1); }else{ System.out.println("Min by Tournament method is: "+minTour2); } //This is Sorting method Arrays.sort(arr); System.out.println("Max by sorting method is: "+arr[arr.length1]); System.out.println("Min by sorting method is: "+arr[0]); } }
 Iterative: ( O ^ n )
Top comments (0)