LeetCode – Matriz de parches (Java)

Dado un número de matriz de enteros positivos ordenados y un número entero n, agregue / parche elementos a la matriz de modo que cualquier número en el rango [1, n] inclusive puede estar formado por la suma de algunos elementos de la matriz. Devuelve el número mínimo de parches necesarios.

Ejemplo 1:
nums = [1, 3], n = 6
Regresar 1.

Análisis

Sea miss el número más pequeño que no se puede formar por la suma de elementos en la matriz. Todos los elementos en [0, miss) can be formed. The miss value starts with 1. If the next number nums[i]<= fallar, entonces el límite se incrementa para ser [0, miss+nums[i]), porque se pueden formar todos los números entre los límites; si el siguiente número nums[i]> miss, eso significa que hay un espacio y necesitamos insertar un número, insertar miss en sí es una elección porque su límite se duplica y cubre todos los números entre los límites [0, miss+miss).

Aquí hay un ejemplo.
Números dados =[1, 4, 10] y n = 50.

miss=1;
i=0, nums[i]<=miss, then miss=1+1=2
i=1, nums[i]>2, then miss = miss+miss = 4
i=1, nums[i]<=miss, then miss = miss+num[i] = 8
i=2, nums[i]>miss, then miss = miss+miss = 16
i=2, nums[i]>miss, then miss = miss+miss = 32
i=2, nums[i]>miss, then miss = miss+miss = 64 
64 > 50. Done! 4 elements are added!

Solución Java

Escribir el código es trivial, una vez que entendemos el algoritmo.

public int minPatches(int[] nums, int n) {
    long miss = 1;
    int count = 0;
    int i = 0;
 
    while(miss <= n){
        if(i<nums.length && nums[i] <= miss){
            miss = miss + nums[i];
            i++;
        }else{
            miss += miss;
            count++;
        }
    }
 
    return count;
}