Given a string consisting of some numbers, not separated by any separator. The numbers are positive integers and the sequence increases by one at each number except the missing number. The task is to complete the function missingNumber which return's the missing number. The numbers will have no more than six digits. Print -1 if input sequence is not valid. 
Note: Its is guaranteed that if the string is valid, then it is sure that atleast one number would be missing from the string.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an string s representing a number.
Output:
For each test case in a new line output will be the missing number. Output will be -1 if the input is invalid.
Constraints:
1<=T<=100
1<=Length of string<=100
Example(To be used only for expected output):
Input:
2
9899100102
1112141519
Output:
101
-1
 
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:
# your task is to complete this function

# function should return the missing number

# else return -1

def missingNumber(string):

    # Code here



Solutions:
def solve(d, k, s, n, ans):
	if k == n:
		return 1
	m = len(d)
	d2 = s[k:k + m]
	if int(d) + 1 == int(d2):
		return solve(d2, k + m, s, n, ans)
	elif int(d) + 2 == int(d2):
		if ans[0] != -1:
			return 0
		ans[0] = int(d) + 1
		return solve(d2, k + m, s, n, ans)
	else:
		d2 = s[k:k + m + 1]
		if int(d) + 1 == int(d2):
			return solve(d2, k + m + 1, s, n, ans)
		elif int(d) + 2 == int(d2):
			if ans[0] != -1:
				return 0
			ans[0] = int(d) + 1
			return solve(d2, k + m + 1, s, n, ans)
	return 0

def missingNumber(s):
	n = len(s)
	ans = [-1]
	for i in range(1, n // 2 + 1):
		ans[0] = -1
		d = s[0:i]
		if solve(d, i, s, n, ans) and ans[0] != -1:
			return ans[0]
	return -1


import math
MAX_DIGITS = 6

def getValue(Str, i, m):
	if i + m > len(Str):
		return -1
	value = 0
	for j in range(m):
		c = ord(Str[i + j]) - ord('0')
		if c < 0 or c > 9:
			return -1
		value = value * 10 + c
	return value

def missingNumber(Str):
	for m in range(1, MAX_DIGITS + 1):
		n = getValue(Str, 0, m)
		if n == -1:
			break
		missingNo = -1
		fail = False
		i = m
		while i != len(Str):
			if missingNo == -1 and getValue(Str, i, 1 + int(math.log10(n + 2))) == n + 2:
				missingNo = n + 1
				n += 2
			elif getValue(Str, i, 1 + int(math.log10(n + 1))) == n + 1:
				n += 1
			else:
				fail = True
				break
			i += 1 + int(math.log10(n))
		if not fail:
			return missingNo
	return -1


def missingNumber(string):
	s = ''
	for i in range(len(string)):
		if i >= 6:
			break
		s += string[i]
		j = i + 1
		s1 = s
		s2 = ''
		f = 0
		while j < len(string):
			s1 = str(int(s1) + 1)
			k = string.find(s1, j)
			if k != -1 and j == k:
				j = j + len(s1)
			else:
				if f:
					break
				f = 1
				s2 = s1
		if f and j >= len(string):
			return int(s2)
	return -1


import math
log10 = lambda n: int(math.log10(n))
getNum = lambda string, i, num_len: int(string[i:i + num_len])

def missingNumber(s):
	for m in range(1, len(s)):
		n = getNum(s, 0, m)
		(i, missing_no, is_valid) = (m, -1, True)
		while i < len(s):
			if getNum(s, i, 1 + log10(n + 1)) == n + 1:
				n += 1
			elif getNum(s, i, 1 + log10(n + 2)) == n + 2:
				missing_no = n + 1
				n += 2
			else:
				is_valid = False
				break
			i += 1 + log10(n)
		if is_valid:
			return missing_no
	return -1


import math
log10 = lambda n: int(math.log10(n))

def getNum(string, i, num_len):
	if i + num_len > len(string):
		return -1
	return int(string[i:i + num_len])

def missingNumber(s):
	max_len = 6
	for m in range(1, max_len + 1):
		n = getNum(s, 0, m)
		if n == -1:
			break
		i = m
		missing_no = -1
		fail = False
		while i < len(s):
			next_one = log10(n + 1)
			next_two = log10(n + 2)
			if getNum(s, i, 1 + next_two) == n + 2:
				missing_no = n + 1
				n += 2
			elif getNum(s, i, 1 + next_one) == n + 1:
				n += 1
			else:
				fail = True
				break
			i += 1 + log10(n)
		if not fail:
			return missing_no
	return -1


import math

def missingNumber(string):

	def getValue(Str, i, m):
		if i + m > len(Str):
			return -1
		value = 0
		for j in range(m):
			c = ord(Str[i + j]) - ord('0')
			if c < 0 or c > 9:
				return -1
			value = value * 10 + c
		return value
	for l in range(1, 7):
		n = getValue(string, 0, l)
		if n == -1:
			return -1
		missing_no = -1
		i = l
		fail = False
		while i < len(string):
			if getValue(string, i, 1 + int(math.log10(n + 2))) == n + 2:
				missing_no = n + 1
				n += 2
			elif getValue(string, i, 1 + int(math.log10(n + 1))) == n + 1:
				n += 1
			else:
				fail = True
				break
			i += 1 + int(math.log10(n))
		if not fail:
			return missing_no
	return -1


def missingNumber(string):

	def rec(ind, prev, f, val):
		if ind == n - 1:
			if f == 1:
				ans[0] = val
			return
		p = ''
		for i in range(ind + 1, n):
			p += string[i]
			if prev == -1:
				rec(i, int(p), 0, val)
				continue
			if int(p) - 1 == prev:
				rec(i, int(p), f, val)
			elif int(p) - 2 == prev and f == 0:
				rec(i, int(p), 1, prev + 1)
	ans = [-1]
	n = len(string)
	rec(-1, -1, 0, -1)
	return ans[0]


def missingNumber(s):
	n = len(s)
	try:
		flag = False
		ans = -2
		for k in range(1, 7):
			ans = -2
			l = k
			n1 = int(s[:l])
			num = n1
			itr = num
			flag = False
			z = l
			i = 0
			flag2 = False
			while i < n:
				if i + z > n:
					flag = False
					ans = -1
					break
				n3 = int(s[i:i + z])
				if len(str(n3 + 1)) > z:
					z += 1
					flag2 = True
				if len(str(n3 + 2)) > z and str(n3 + 1) != s[i + z:i + 2 * z]:
					z += 1
					flag2 = True
				if i == 0:
					itr = n3
					if flag2 == False:
						i += z
					else:
						i += z - 1
						flag2 = False
					continue
				if flag == False and n3 - itr == 2:
					ans = int(n3) - 1
					flag = True
					itr += 2
				elif flag == True and n3 - itr == 2:
					flag = False
					ans = -1
					break
				elif n3 - itr == 1:
					itr += 1
				elif n3 - itr == 0:
					flag = False
					ans = -1
					break
				elif n3 - itr > 2:
					flag = False
					ans = -1
					break
				if flag2 == False:
					i += z
				else:
					i += z - 1
					flag2 = False
			if flag:
				return ans
		return -1
	except:
		num = int(s[0])
		return -1


def missingNumber(string):
	arr = [i for i in string]
	for i in range(1, 7):
		prev = -1
		j = 0
		missing = []
		gap = i
		while j + gap <= len(string):
			temp = int(''.join(arr[j:j + gap]))
			if prev != -1:
				if prev == int(''.join(['9' for j in range(gap - 1)] + ['8'])) and j + gap < len(arr) and (temp * 10 + int(arr[j + gap]) == int(''.join(['1'] + ['0' for j in range(gap)]))):
					missing.append(prev + 1)
					gap += 1
					temp = temp * 10 + int(arr[j + gap - 1])
				elif temp - 1 == prev:
					pass
				elif temp - 2 == prev:
					missing.append(temp - 1)
				else:
					break
				prev = temp
			else:
				prev = temp
			j = j + gap
			nine = int(''.join(['9' for j in range(gap)]))
			if temp == nine:
				gap += 1
		if j == len(string) and len(missing) == 1:
			return missing[0]
	return -1


def missingNumber(inp):

	def startswith(idx, num):
		num = str(num)
		if len(num) > len(inp) - idx:
			return False
		i = 0
		while idx < len(inp) and i < len(num):
			if inp[idx] != num[i]:
				return False
			i += 1
			idx += 1
		return True

	def isContinousSeq(startIndex, num):
		if startIndex >= len(inp):
			return True
		if len(str(num)) > len(inp) - startIndex:
			return False
		return isContinousSeq(startIndex + len(str(num)), num + 1) if startswith(startIndex, num) else False

	def findFirstMismatch(idx, num):
		if startswith(idx, num):
			return findFirstMismatch(idx + len(str(num)), num + 1)
		return (idx, num)
	for d in range(1, min(len(inp) + 1, 7)):
		first = int(inp[:d])
		(firstMismatchIdx, miss) = findFirstMismatch(0, first)
		if firstMismatchIdx >= len(inp):
			continue
		if isContinousSeq(firstMismatchIdx, miss + 1):
			return miss
	return -1


from math import log

def missingNumber(string):

	def get_int(string, st, ed):
		if ed > len(string):
			return -1
		return int(string[st:ed])
	k = 1
	for k in range(1, 7):
		num = get_int(string, 0, k)
		i = k
		missing = -1
		flag = True
		if num < 0:
			break
		j = i
		while j < len(string):
			nxt_str = get_int(string, j, j + 1 + int(log(num + 1, 10)))
			nxt_nxt_str = get_int(string, j, j + 1 + int(log(num + 2, 10)))
			if num + 1 == nxt_str:
				num += 1
			elif missing == -1 and num + 2 == nxt_nxt_str:
				missing = num + 1
				num += 2
			else:
				flag = False
				break
			j += 1 + int(log(num, 10))
		if flag:
			return missing
	return -1


import math
MAX_DIGITS = 6

def getValue(Str, i, n):
	if i + n > len(Str):
		return -1
	return int(Str[i:i + n])

def missingNumber(Str):
	for m in range(1, MAX_DIGITS + 1):
		n = getValue(Str, 0, m)
		if n == -1:
			break
		mn = -1
		fail = False
		i = m
		while i != len(Str):
			if mn == -1 and getValue(Str, i, 1 + int(math.log10(n + 2))) == n + 2:
				mn = n + 1
				n += 2
			elif getValue(Str, i, 1 + int(math.log10(n + 1))) == n + 1:
				n += 1
			else:
				fail = True
				break
			i += 1 + int(math.log10(n))
		if not fail:
			return mn
	return -1


import math

def val(s, i, l):
	if i + l > len(s):
		return -1
	value = 0
	for j in range(l):
		c = ord(s[i + j]) - ord('0')
		if c < 0 or c > 9:
			return -1
		value *= 10
		value += c
	return value

def missingNumber(s):
	for l in range(1, 7):
		n = val(s, 0, l)
		if n == -1:
			break
		ans = -1
		fail = False
		i = l
		while i != len(s):
			if ans == -1 and val(s, i, 1 + int(math.log10(n + 2))) == n + 2:
				ans = n + 1
				n += 2
			elif val(s, i, 1 + int(math.log10(n + 1))) == n + 1:
				n += 1
			else:
				fail = True
				break
			i += 1 + int(math.log10(n))
		if not fail:
			return ans
	return -1


def missingNumber(string):
	l = 1
	while l <= 6:
		curr_len = l
		found = False
		if curr_len >= len(string):
			break
		num = string[:curr_len]
		index = curr_len
		while index < len(string):
			next_num = string[index:index + curr_len]
			if int(num) + 1 == int(next_num):
				num = next_num
			elif int(num) + 2 == int(next_num) and (not found):
				ans = int(num) + 1
				num = next_num
				found = True
			elif not found and index + curr_len < len(string) and (int(num) + 2 == int(next_num + string[index + curr_len])):
				found = True
				ans = int(num) + 1
				num = next_num + string[index + curr_len]
				curr_len += 1
			else:
				found = False
				break
			index += curr_len
			if num == '9' * curr_len:
				curr_len += 1
		if found:
			return str(ans)
		l += 1
	return -1


def missingNumber(string):

	def sto(s):
		x = 0
		for i in s:
			x = x * 10 + (ord(i) - ord('0'))
		return x
	n = len(string)
	for k in range(1, 7):
		temp = ''
		l = k
		i = 0
		while i < n and l > 0:
			temp += string[i]
			i += 1
			l -= 1
		prev = sto(temp)
		count = 0
		j = i
		miss = 0
		flag = 0
		temp = ''
		while j < n:
			temp += string[j]
			j += 1
			if prev + 1 == sto(temp):
				prev = sto(temp)
				temp = ''
			elif prev + 2 == sto(temp):
				count += 1
				miss = prev + 1
				prev = sto(temp)
				temp = ''
			elif prev < sto(temp):
				flag = 1
		if flag == 0 and count == 1:
			return miss
	return -1


def valid(string, i):
	index = 0
	x = int(string[:i])
	list = [x]
	a = len(str(x))
	index += a
	while index < len(string):
		x += 1
		a = len(str(x))
		if index + a < len(string):
			if x == int(string[index:index + a]):
				list.append(int(string[index:index + a]))
				x = int(string[index:index + a])
			else:
				temp = x + 1
				a = len(str(temp))
				if x + 1 == int(string[index:index + a]):
					list.append(int(string[index:index + a]))
			index += a
		else:
			list.append(int(string[index:]))
			index = len(string)
	temp = list[0]
	ans = []
	if len(list) == 2:
		if list[0] + 1 != list[1]:
			if list[0] + 2 == list[1]:
				return list[0] + 1
			else:
				return -1
	for i in range(1, len(list)):
		if list[i - 1] + 1 == list[i]:
			continue
		elif list[i - 1] + 2 == list[i]:
			ans.append(list[i - 1] + 1)
		else:
			ans.append('*')
	if len(ans) > 1 or len(ans) == 0:
		return -1
	elif ans[0] != '*':
		return ans[0]
	else:
		return -1

def missingNumber(string):
	for i in range(1, 7):
		x = valid(string, i)
		if x != -1:
			return x
	return -1


def missingNumber(string):
	size = len(string)
	for l in range(1, 7, 1):
		prev = int(string[:l])
		temp = ''
		ptr = l
		flag = 0
		ans = -1
		count = 0
		while ptr < size:
			temp += string[ptr]
			ptr += 1
			if prev + 1 == int(temp):
				prev = int(temp)
				temp = ''
			elif prev + 2 == int(temp):
				count += 1
				ans = prev + 1
				prev = int(temp)
				temp = ''
			elif prev < int(temp):
				flag = 1
				break
		if count == 1 and flag == 0:
			break
	return ans


def missingNumber(s):
	for i in range(min(6, len(s))):
		s1 = int(s[0:i + 1])
		x = i + 1
		l = []
		for j in range(i + 1, len(s)):
			if j == len(s) - 1:
				y = int(s[x:j + 1])
				if s1 > y:
					break
				if s1 + 2 < y:
					break
				if s1 + 2 == y:
					l.append(s1 + 1)
					break
			if int(s[x:j + 1]) - 1 == s1:
				s1 = int(s[x:j + 1])
				x = j + 1
				continue
			if int(s[x:j + 1]) - 2 == s1:
				l.append(s1 + 1)
				s1 = int(s[x:j + 1])
				x = j + 1
				continue
			if int(s[x:j + 1]) - 2 > s1:
				break
		if len(l) == 1:
			return l[0]
	return -1


def missingNumber(string):
	m = 1
	s = ''
	s = string
	num = s[:m]
	start = len(num)
	while start < len(s):
		next_ = [int(num) + 1, int(num) + 2]
		if not (int(s[start:start + len(str(next_[0]))]) == next_[0] or int(s[start:start + len(str(next_[1]))]) == next_[1]):
			m += 1
			check = False
			num = s[:m]
			start = len(num)
		elif int(s[start:start + len(str(next_[0]))]) == next_[0] and int(s[start:start + len(str(next_[1]))]) != next_[1]:
			num = str(next_[0])
			start += len(num)
			check = True
		elif int(s[start:start + len(str(next_[0]))]) != next_[0] and int(s[start:start + len(str(next_[1]))]) == next_[1]:
			missing = int(next_[0])
			num = str(next_[1])
			start += len(num)
			check = True
	if check and 'missing' in locals():
		return missing
	else:
		return -1


def missingNumber(s):
	n = len(s)
	for i in range(1, 7):
		miss = 0
		x = s[:i]
		new = ''
		ans = []
		while miss < 2 and s != new:
			if new + x not in s:
				miss += 1
				ans.append(x)
			else:
				new += x
			x = str(int(x) + 1)
		if new == s and len(ans) == 1:
			return ans[0]
	return -1