Ice Cream Parlor

  • + 1 comment
    public class Solution {
        static void quickSort(int[] arr, int hi, int lo){
            if(lo<hi){
                int pi = partition(arr,lo,hi);
                quickSort(arr,lo,pi-1);
                quickSort(arr,pi+1,hi);
            }
        }
        static int partition(int[] arr,int lo,int hi){
            int pivot = arr[hi];
            int i = lo-1;
            for(int j=lo; j<hi; j++){
                if(arr[j]<=pivot){
                    i++;
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
            int temp = arr[i+1];
            arr[i+1] = arr[hi];
            arr[hi] = temp;
            return i+1;
        } 
    
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int t = scan.nextInt();     //total number of testcases
            for(int x=0;x<t;x++){
                int m = scan.nextInt(); //total money available
                int n = scan.nextInt(); //total varieties of ice-cream
                int[] arr = new int[n]; //array of prices
                for(int i=0;i<n;i++){
                    arr[i] = scan.nextInt();
                }
                int sum, min_sum = 999999;
               int l=0,r=n-1;
                int min_l = l, min_r = r;
                quickSort(arr,l,r);
                while(l<r){
                    sum = arr[l] +arr[r];
                     if(Math.abs(sum) < Math.abs(min_sum))
            {
              min_sum = sum;
              min_l = l;
              min_r = r;
            }
                    if(sum==m) break;
                    else if(sum<m) l++;
                    else r--;
                }
                System.out.println((min_l+1)+" "+(min_r+1));
                
            }
        }
    }