Find the Missing Number II(ladder)

Description

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

Notice  
n <= 30

Example
Given n = 20, str = 19201234567891011121314151618
return 17

Assumption

How about large n? if n > INT_32MAX ?
Full string calculate ?
Not only one decode way? or No decode way?
If missing more than one?

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param n an integer
     * @param str a string with number from 1-n in 
     *            random order and miss one number
     * @return an integer
     */
    int findMissing2(int n, string& str) {
        if (n < 1) {
            return -1;
        }
        vector<bool> used(n + 1, false);
        return findHelper(n, str, 0, used);
    }
    int findHelper(int n, string& str, int start, vector<bool>& used) {
        // when getting full decode nums
        if (start == str.size()) {
            vector<int> result;
            for (int i = 1; i <= n; ++i) {
                if (used[i] == false) {
                    result.push_back(i);
                }
            }
            if (result.size() == 1) {
                return result[0];
            }
            return -1;
        }
        // dfs
        // if num begins with '0'
        if (str[start] == '0') {
            return -1;
        }
        // text next 1 or 2 string to int
        for (int i = 1; i < 3; ++i) {
            int num = convertToInt(str, start, i);
            // 1 <= num <= n, and num is unique
            if (num >= 1 && num <= n && used[num] == false) {
                used[num] = true;
                int next = findHelper(n, str, start + i, used);
                if (next != -1) {
                    return next;
                }
                used[num] = false;
            }
        }
        return -1;
    }
    int convertToInt(string& str, int start, int len) {
        return stoi(str.substr(start, len));
    }
};

Similar problems

Find the Missing Number
First Missing Positive

Tags

Backtracking Depth First Search