import java.util.Arrays;

public class Main {
    public static int findMinNonCreatableSum(int[] coins) {
        // Sort the array
        Arrays.sort(coins);
        
        // Initialize max creatable sum
        int maxCreatable = 0;
        
        // Iterate through coins
        for (int coin : coins) {
            // If current coin is greater than maxCreatable + 1,
            // we found our answer
            if (coin > maxCreatable + 1) {
                return maxCreatable + 1;
            }
            // Add current coin to maxCreatable
            maxCreatable += coin;
        }
        
        // If we can create all sums up to maxCreatable,
        // the answer is maxCreatable + 1
        return maxCreatable + 1;
    }

    public static void main(String[] args) {
        int[] coins = {2, 9, 1, 2, 7};
        int result = findMinNonCreatableSum(coins);
        System.out.println("Smallest sum that cannot be created: " + result);
    }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode handler = head;
        while(l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                handler.next = l1;
                l1 = l1.next;
            } else {
                handler.next = l2;
                l2 = l2.next;
            }
            handler = handler.next;
        }
        
        if (l1 != null) {
            handler.next = l1;
        } else if (l2 != null) {
            handler.next = l2;
        }
        
        return head.next;
    }
}

import java.util.Arrays;
 
public class QuickSortMain {
 
    private static int array[];
 
    public static void sort(int[] arr) {
 
        if (arr == null || arr.length == 0) {
            return;
        }
        array = arr;
        quickSort(0, array.length-1);
    }
 
    private static void quickSort(int left, int right) {
 
        int i = left;
        int j = right;
        // find pivot number, we will take it as mid
        int pivot = array[left+(right-left)/2];
 
        while (i <= j) {
            /**
             * In each iteration, we will increment left until we find element greater than pivot
             * We will decrement right until we find element less than pivot
             */
            while (array[i] < pivot) { i++; } while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (left < j)
            quickSort(left, j);
        if (i < right)
            quickSort(i, right);
    }
 
    private static void exchange(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
    public static void main(String a[]){
        int[] input = {33,21,45,64,55,34,11,8,3,5,1};
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(input));
        sort(input);
        System.out.println("==================");
        System.out.println("After Sorting : ");
        System.out.println(Arrays.toString(array));
 
    }
}

import java.util.*;
 
public class HeapSortMain {
 
   public static void buildheap(int []arr) {
 
    /*
     * As last non leaf node will be at (arr.length-1)/2 
     * so we will start from this location for heapifying the elements
     * */
    for(int i=(arr.length-1)/2; i>=0; i--){
           heapify(arr,i,arr.length-1);
      }
   }
 
   public static void heapify(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
         max=left;
      } else {
         max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
         max=right;
      }
      // If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }
 
   public static void exchange(int[] arr,int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t; 
   }
 
   public static int[] heapSort(int[] arr) {
 
      buildheap(arr);
      int sizeOfHeap=arr.length-1;
      for(int i=sizeOfHeap; i>0; i--) {
         exchange(arr,0, i);
         sizeOfHeap=sizeOfHeap-1;
         heapify(arr, 0,sizeOfHeap);
      }
      return arr;
   }
 
   public static void main(String[] args) {
      int[] arr={1,10,16,19,3,5};
      System.out.println("Before Heap Sort : ");
      System.out.println(Arrays.toString(arr));
      arr=heapSort(arr);
      System.out.println("=====================");
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(arr));
   }
}

import static java.lang.System.*;
import java.util.Arrays;        

public class MergeSort{

private static int passCount;

public static void mergeSort(int[] list)
{
    passCount=0;
    mergeSort(list, 0, list.length);
}

private static void mergeSort(int[] list, int front, int back)  //O( Log N )
{
    int mid = (front+back)/2;
    if(mid==front) return;
    mergeSort(list, front, mid);
    mergeSort(list, mid, back);
    merge(list, front, back);

}

private static void merge(int[] list, int front, int back)  //O(N)
{
   int dif = back-front;
   int[] temp = new int[dif];
   int beg = front, mid = (front+back)/2;
   int saveMid = mid;
   int spot = 0;

   while(beg < saveMid && mid < back) {
      if(list[beg] < list[mid]) {
         temp[spot++] = list[beg++];
      } else {
         temp[spot++] = list[mid++];
      }
   }
   while(beg < saveMid)
      temp[spot++] = list[beg++];
   while(mid < back)
      temp[spot++] = list[mid++];
   for(int i = 0; i < back-front; i++) {
      list[front+i] = temp[i];
   }
    System.out.println("pass " + passCount++ + " " + Arrays.toString(list) + "\n");
  }
  
  
    public static void main(String args[])
    {
        mergeSort(new Comparable[]{ 9, 5, 3, 2 });
        System.out.println("\n");
        
        mergeSort(new Comparable[]{ 19, 52, 3, 2, 7, 21 });
        System.out.println("\n");
        
        mergeSort(new Comparable[]{ 68, 66, 11, 2, 42, 31});
        System.out.println("\n");
    }
  
 }