The minimum non composable sum of arrays

author ：Grey

Original address ： The minimum non composable sum of arrays

Title Description

link ：https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
source ： Cattle from

Given an array of all positive numbers arr, Define it arr The concept of minimum non composable sum of ：

1,arr All non empty subsets of , Adding up all the elements in each subset will produce a lot of values , The smallest of them is recorded as min, The biggest is recorded as max;

2, In the interval [min,max] On , If there are some positive numbers that cannot be arr Add a subset to get , So the smallest of these positive numbers , Namely arr The minimum non composable sum of ;

3, In the interval [min,max] On , If all numbers can be arr Add a subset of to get , that max+1 yes arr The minimum non composable sum of ;

give an example ： arr = {3,2,5}

arr Of min by 2,max by 10,

In the interval [2,10] On ,4 Is the smallest value that cannot be added by any subset , therefore 4 yes arr The minimum non composable sum of ;

arr = {3,2,4}

arr Of min by 2,max by 9,

In the interval [2,9] On ,8 Is the smallest value that cannot be added by any subset , therefore 8 yes arr The minimum non composable sum of ;

arr = {3,1,2} arr Of min by 1,max by 6,

In the interval [2,6] On , Any number can be added by a subset to get , therefore 7 yes arr The minimum non composable sum of ;

Please write the function to return arr The minimum non composable sum of .

Ideas

First we set two variables ,max and min Used to record the maximum value obtained by the accumulation of arrays , And the minimum value accumulated when the array is not empty . Then in the non empty state of the array , The cumulative sum must be [min, max] Within the interval . We set up

boolean[][] dp = new boolean[arr.length][max + 1];

among dp[i][j] Express [0....i] The elements in the range are accumulated arbitrarily , Can you make up j This cumulative sum .

Obviously there is

// 0 Elements can form arr[0] This cumulative sum 
dp[0][arr[0]] = true;

for (int i = 0; i < dp.length; i++) {
    
     // 0..i The last element is not used , It can make up 0 This cumulative sum 
     dp[i][0] = true;
}

So we get dp The first row and the first column of this array .

Then we can deduce the universal position

dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);

The meaning of ：

[0...i] Within the scope of , Arbitrary choice , Can you make up j This cumulative sum , In fact, it includes two cases ：

situation 1：[0...i-1] Within the scope of , Arbitrary choice , Can you make up j This cumulative sum , If possible , explain dp[i][j]=true

situation 2：[0...i-1] Within the scope of , Arbitrary choice , Can you make up j-arr[i] This cumulative sum （ Be careful not to cross the line ）, If possible , explain dp[i][j] = true

therefore , The general position is determined as follows

        for (int i = 1; i < dp.length; i++) {
    
            for (int j = 1; j < max + 1; j++) {
    
                dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
            }
        }

After the above treatment ,dp Completed , The next step is judgment dp The first is false The location of , Is the answer

        for (int i = min; i <= max; i++) {
    
            if (!dp[arr.length - 1][i]) {
    
                return i;
            }
        }

If the above process does not find , Then return to max+1, The complete code is as follows

    public static int getFirstUnFormedNum(int[] arr) {
    
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
    
            max += arr[i];
            min = Math.min(min, arr[i]);
        }
        //  The range that can be reached is [min,max]
        // dp[i][j] 0....i Can you make up j
        boolean[][] dp = new boolean[arr.length][max + 1];
        //  The first 0 That's ok   Except for the following positions , The other positions are false
        dp[0][arr[0]] = true;
        for (int i = 0; i < dp.length; i++) {
    
            // 0..i The last element is not used , It can make up 0 This cumulative sum 
            dp[i][0] = true;
        }
        for (int i = 1; i < dp.length; i++) {
    
            for (int j = 1; j < max + 1; j++) {
    
                dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
            }
        }
        for (int i = min; i <= max; i++) {
    
            if (!dp[arr.length - 1][i]) {
    
                return i;
            }
        }
        return max + 1;
    }

Advanced

link ：https://www.nowcoder.com/questionTerminal/a689a05f75ff4caaa129b1f971aeb71e
source ： Cattle from

Given an array of positive numbers arr, Where all values are integers , The following is the concept of minimum non composable sum

• ​ hold arr All the elements in each subset add up to many values , The smallest of them is recorded as min, The biggest is recorded as max

• ​ In the interval [min, max] On , If there are several, it can not be arr Add a subset to get , Then the smallest number is arr The minimum non composable sum of

• ​ In the interval [min, max] On , If all numbers can be arr Add a subset of to get , that max+1 yes arr The minimum non composable sum of

  Please write a function to return a positive array arr The minimum non composable sum of

  Guarantee 1 There must have been ！

  The time complexity is O(n), The extra space complexity is O(1)

Main idea ：

If there must be 1 The number of , So if you sort this positive array ,0 The value on the position must be 1, Set a variable range, The initial value is 1, Indicates the range of the smallest positive integer that can be solved at present ,

Next, we'll expand by traversing the entire array range The scope of the , hypothesis [0.....i-1] Can make range Expand to b This value ,i The value at position is assumed to be a, If

a <= b + 1

Traverse to i Location , It can make range The value of is extended to a + b,

If

a > b + 1

be b + 1 Is the smallest non composable sum of the entire array , Can return directly . The complete code is as follows ：

    public static long unformedSum(long[] arr) {
    
        if (arr == null || arr.length == 0) {
    
            return 0;
        }
        Arrays.sort(arr);
        long range = 1;
        for (int i = 1; i != arr.length; i++) {
    
            if (arr[i] > range + 1) {
    
                return range + 1;
            } else {
    
                range += arr[i];
            }
        }
        return range + 1;
    }

more

Algorithm and data structure notes