package main

import (
    "fmt"
    "math"
    "sort"
)

func main() {
    arr := []int{1, 2, 31, 33}

    if true {
        ret := minPatches(arr, 555)
        fmt.Println(ret)
    }

    if true {
        ret := minPatches2(arr, 555)
        fmt.Println(ret)
    }
}

// arr请保证有序，且正数  1~aim
func minPatches(arr []int, aim int) int {
    patches := 0 // 缺多少个数字
    range2 := 0  // 已经完成了1 ~ range的目标
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] < arr[j]
    })
    for i := 0; i != len(arr); i++ {
        // arr[i]
        // 要求：1 ~ arr[i]-1 范围被搞定！
        for arr[i]-1 > range2 { // arr[i] 1 ~ arr[i]-1
            range2 += range2 + 1 // range + 1 是缺的数字
            patches++
            if range2 >= aim {
                return patches
            }
        }
        // 要求被满足了！
        range2 += arr[i]
        if range2 >= aim {
            return patches
        }
    }
    for aim >= range2+1 {
        range2 += range2 + 1
        patches++
    }
    return patches
}

// 嘚瑟
func minPatches2(arr []int, K int) int {
    patches := 0 // 缺多少个数字
    range2 := 0  // 已经完成了1 ~ range的目标
    for i := 0; i != len(arr); i++ {
        // 1~range
        // 1 ~ arr[i]-1
        for arr[i] > range2+1 { // arr[i] 1 ~ arr[i]-1

            if range2 > math.MaxInt64-range2-1 {
                return patches + 1
            }

            range2 += range2 + 1 // range + 1 是缺的数字
            patches++
            if range2 >= K {
                return patches
            }
        }
        if range2 > math.MaxInt64-arr[i] {
            return patches
        }
        range2 += arr[i]
        if range2 >= K {
            return patches
        }
    }
    for K >= range2+1 {
        if K == range2 && K == math.MaxInt64 {
            return patches
        }
        if range2 > math.MaxInt64-range2-1 {
            return patches + 1
        }
        range2 += range2 + 1
        patches++
    }
    return patches
}