Find the Missing Number II

Giving a string with number from 1-n in random order, but miss 1 number. Find that number.

Example:

Given n = 20, str = 19201234567891011121314151618

return 17

Solution:

This problem can be solved by depth first search.

• initialize a foundNums boolean array with false value for number from 1 to n.
• If the first digit is less than n, set it as found in foundNums and check the remaining part.
• If the first two digits are less than n, set this number as found in foundNums and check the remaining part.
• Stop when no more digit left, and return the only missing number in foundNums.

Code:

public class Solution {

    private int result = 0;

    public int findMissing2(int n, String str) {
        dfs(0, n, str, new boolean[n + 1]);
        return result;
    }

    private void dfs(int idx, int n, String str, boolean[] foundNums) {
        if (idx >= str.length()) {
            int count = 0;
            int firstI = 0;
            for (int i = 1; i <= n; i++) {
                if (!foundNums[i]) {
                    count++;
                    firstI = i;
                }

            }
            if (count == 1) {
                result = firstI;
            }
            return;
        }
        //one digits
        int num = (int)(str.charAt(idx) - '0');
        if (num <= n && !foundNums[num]) {
            foundNums[num] = true;
            dfs(idx + 1, n, str, foundNums);
            foundNums[num] = false;
        }

        //two digits
        if (idx + 1 >= str.length()) {
            return;
        }
        num = num * 10 + (int)(str.charAt(idx + 1) - '0');
        if (num <= n && !foundNums[num]) {
            foundNums[num] = true;
            dfs(idx + 2, n, str, foundNums);
            foundNums[num] = false;
        }
    }
}