Combine K elementos mínimos de la array hasta que solo haya un elemento

Dada una array arr[] y un entero K , la tarea es fusionar K elementos mínimos de la array hasta que solo quede un elemento en la array.
Nota: Si es imposible fusionarse en un solo elemento, imprima -1. 
 

Entrada: arr[] = {3, 2, 4, 1}, K = 2 
Salida: 10 
Explicación: 
fusionar K elementos mínimos de la array ({3, 2, 4, 1}) = 1 + 2 = 3 
después de fusionar la array será {3, 3, 4} 
Fusionar K elementos mínimos de la array ({3, 3, 4}) = 3 + 3 = 6 
Después de fusionar la array será {4, 6} 
Fusionar K elementos mínimos de la Array ({4, 6}) = 4 + 6 = 10
Entrada: arr[] = {3, 2, 4, 1}, K = 3 
Salida: -1 
Explicación: 
Después de fusionar quedarán dos elementos {6, 4} que no se puede fusionar más. 
 

Enfoque: la idea es ordenar la array y luego fusionar los primeros K elementos mínimos de la array en un elemento, luego insertar el elemento en la array en su posición ordenada en la array con la ayuda de Binary Search . Del mismo modo, repita este paso hasta que solo quede un elemento en la array. Si al final quedan menos de K elementos, devuelve -1.
A continuación se muestra la implementación del enfoque anterior: 
 

// Java implementation to merge the
// K minimum elements of the Array
// until there is only one element
// is left in the array
 
// Imports
import java.io.*;
import java.lang.*;
import java.util.*;
 
 
class GFG {
     
    // Function to merge the element
    // of the array until there is
    // only one element left in array
    public static int mergeStones(
        List<Integer> list, final int k) {
         
        // Sorting the array
        Collections.sort(list);
        int cost = 0;
         
        // Loop to merge the elements
        // until there is element
        // greater than K elements
        while(list.size() > k) {
            int sum = 0;
             
            // Merging the K minimum
            // elements of the array
            for(int i = 0; i < k; i++) {
                sum += list.get(i);
            }
             
            // Removing the K minimum
            // elements of the array
            list.subList(0, k).clear();
             
            // Inserting the merged
            // element into the array
            insertInSortedList(list, sum);
            cost += sum;
        }
         
        // If there is only K element
        // left then return the element
        if(list.size() == k) {
            cost += list.stream().reduce(
                         0, Integer::sum);
            return cost;
        } else {
            return -1;
        }
    }
     
    // Function insert the element into
    // the sorted position in the array
    public static void insertInSortedList(
        List<Integer> sortedList, int item) {
        int len = sortedList.size();
        insertInSortedList(sortedList, item,
                                 0, len - 1);
    }
     
    // Utility function to insert into the
    // array with the help of the position
    public static void insertInSortedList(
        List<Integer> sortedList, int item,
                       int start, int end) {
        int mid = (int) ((end - start)/ 2.00);
        if(mid == 0 ||
             (mid == sortedList.size() - 1) ||
                sortedList.get(mid) == item) {
            sortedList.add(mid, item);
            return;
        }
        else if(sortedList.get(mid) < item) {
            insertInSortedList(sortedList,
                       item, mid + 1, end);
        } else {
            insertInSortedList(sortedList,
                     item, start, mid - 1);
        }
    }
     
    // Driver Code
    public static void main(String [] args) {
        List<Integer> stones = new ArrayList<>();
        stones.add(3);
        stones.add(2);
        stones.add(4);
        stones.add(1);
        System.out.println(mergeStones(stones, 3));
        System.out.println(mergeStones(stones, 2));
    }
}

# Python implementation to merge the K minimum elements of the array
# until there is only one element is left in the array
class GFG:
 
    # Utility function to insert the element at its correct position in a sorted array
    # (Binary search is used to get the index of the correct position)
    def insertInSortedList(self, sortedList, item, start, end):
        mid = start + (end - start) // 2
        if mid == 0 or mid == end - 1 or sortedList[mid] == item:
            sortedList.insert(mid, item)
            return
        elif sortedList[mid] < item:
            self.insertInSortedList(sortedList, item, mid + 1, end)
        else:
            self.insertInSortedList(sortedList, item, start, mid - 1)
 
    # Function to merge the element of the array until there is
    # only one element left in array
    def mergeStones(self, List, k):
 
        # Sort the array
        List.sort()
 
        cost = 0
 
        # Loop to merge the elements until there are
        # greater than K elements in the array
        while len(List) > k:
            Sum = 0
 
            # Obtain the sum of K minimum elements
            for i in range(k):
                Sum += List[i]
 
            # Remove the K minimum elements from the array
            for _ in range(k):
                List.pop(0)
 
            # Insert the merged element into the sorted array
            # at its correct position
            self.insertInSortedList(List, Sum, 0, len(List))
            cost += Sum
 
        # If there are only K elements left,
        # take the sum and return the sum, else return -1
        if len(List) == k:
            cost += sum(List[:])
            return cost
        else:
            return -1
 
# Driver code
if __name__ == '__main__':
    stones = []
    stones.append(3)
    stones.append(2)
    stones.append(4)
    stones.append(1)
    print(GFG().mergeStones(stones, 3))
    print(GFG().mergeStones(stones, 2))
     
    # This code is contributed by keshavrathi

-1
10