Lintcode 570. Find the Missing Number II

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

Example

Example1

Input: n = 20 and str = 19201234567891011121314151618
Output: 17
Explanation:
19'20'1'2'3'4'5'6'7'8'9'10'11'12'13'14'15'16'18

Example2

Input: n = 6 and str = 56412
Output: 3
Explanation:
5'6'4'1'2

Notice

n <= 30
Data guarantees have only one solution

Code (Java):

public class Solution {
    /**
     * @param n: An integer
     * @param str: a string with number from 1-n in random order and miss one number
     * @return: An integer
     */
    private int sum = 0;
    public int findMissing2(int n, String str) {
        // write your code here
        if (n <= 0 || str == null || str.length() == 0) {
            return 0;
        }
        boolean[] visited = new boolean[n + 1];

        findMissing2Helper(n, str, 0, 0, visited);

        int target = (1 + n) * n / 2;

        return target - sum;
    }

    private boolean findMissing2Helper(int n, String str, int startIdx, int curSum, boolean[] visited) {
        if (startIdx >= str.length()) {
            sum = curSum;
            return true;
        }

        for (int i = 1; i <= 2; i++) {
            if (startIdx + i > str.length()) {
                return false;
            }
            
            String substr = str.substring(startIdx, startIdx + i);
            
            if (substr.charAt(0) == '0') {
                return false;
            }

            int val = Integer.parseInt(substr);
            if (val <= n && !visited[val]) {
                visited[val] = true;
                boolean found = findMissing2Helper(n, str, startIdx + i, curSum + val, visited);
                if (found) {
                    return true;
                }
                visited[val] = false;
            }
        }

        return  false;
    }
}