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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

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;     } }