## Find The Missing Number

### June 26, 2015

This is harder than it looks. One problem is that the length of the numbers may increase in the middle of the string; for instance, the string 99989999… begins with four-digit numbers but the next number has five digits. Another problem is that the beginning of the string may make it difficult to determine the length of the numbers; for instance, is a string that begins 9899… the beginning of the sequence 98, 99, … or the sequence 989, 990, …?

```(define (next str)   (number->string (+ (string->number str) 1)))```

```(define (missing-from start rest)   (let ((len (string-length rest)))     (if (zero? len) -1       (let* ((n (next start))              (n-len (string-length n)))         (if (and (<= n-len len)                  (string=? n (substring rest 0 n-len)))             (missing-from n (substring rest n-len len))             (let* ((n1 (next n)) (n1-len (string-length n1)))               (if (none-missing n1 (substring rest n1-len len))                   (string->number n) -1)))))))```

```(define (none-missing start rest)   (let ((len (string-length rest)))     (or (zero? len)         (let* ((n (next start)) (n-len (string-length n)))             (and (<= n-len len)                  (string=? n (substring rest 0 n-len))                  (none-missing n (substring rest n-len len)))))))```

```(define (missing-number str)   (let ((len (string-length str)))     (let loop ((m 1))       (let* ((left (substring str 0 m))              (right (substring str m len))              (n (missing-from left right)))         (if (negative? n) (loop (+ m 1)) n)))))```

The `next` function does string arithmetic to increment its argument. The `missing-from` returns the first missing number in a string, or -1 if it reaches the end of the string without finding a miss. The `none-missing` function ensures there are no more missing numbers after the first. And the `missing-number` function starts the process. Here are some examples:

```> (missing-number "12346789") 5 > (missing-number "26272829313233") 30 > (missing-number "9293949596979899101") 100 > (missing-number "9294959697") 93 > (missing-number "99101102103104105") 100 > (missing-number "596597598600601602") 599 > (missing-number "989999009901990299049905") 9903 > (missing-number "98999901990299039904") 9900 > (missing-number "9998999910000100011000210004") 10003 > (missing-number "9899101102") 100```

You can run the program at http://ideone.com/9c37Uh.

Pages: 1 2

### 27 Responses to “Find The Missing Number”

1. FA said

Scala

def check(input: String, size: Int = 1): String = {
if (size > 5) “No solution”
else {
if (input.length x.toInt).sliding(2, 1).toList
val nrOnes = pairs.filter(x => x(1) – x(0) == 1).size
val nrTwo = pairs.filter(x => x(1) – x(0) == 2).size
if (nrOnes == pairs.size – 1 && nrTwo == 1) (pairs.filter(x => x(1) – x(0) == 2)(0)(1) – 1).toString
else check(input, size + 1);
}
}
} //> check: (input: String, size: Int)String

check(“596597598600601602”) //> res0: String = 599
check(“1”) //> res1: String = No solution
check(“12346”) //> res2: String = 5

2. Rutger said

Quick ugly Python list comprehension inefficient solution.

```for v in ['12356', '596597598600601602','1234512346123471234912350']:
for digit_length in range(1,6):
numbers = [int(v[i:i+digit_length]) for i in range(0, len(v), digit_length)]
if len(numbers) > 1 and all([(1 <= (tup[1] - tup[0]) <= 2) for tup in zip(numbers, numbers[1:])]) > 0:
print (set(range(numbers[0], numbers[-1]+1)) - set(numbers)).pop()
```

Prints:
4
599
12348

3. Rutger said

Oh yea, that > 0 on line 4 is super hilarious, but that is the beauty of solving it in few minutes :)

4. Paul said

In Python3.

```def readnext(s, i, length, expected):
for L in range(2):
b = int(s[i:i+length + L])
if b in (expected, expected + 1):
return b, i + length + L
return False

def missing_number(s):
n = len(s)
for length in range(1, 6):
curr = int(s[:length])
i = length
cand = None
while i < n:
rn = readnext(s, i, length, curr + 1)
if not rn:
break
alternative = curr + 2
curr, i = rn
if curr == alternative:
if cand:
break
cand = curr - 1
if cand and i >= n:
return cand

import random
for case in range(100000):
start = random.randrange(10, 100000)
n = random.randrange(5, 20)
seq = list(range(start, start + n))
missing = seq.pop(random.randrange(1, n-1))
nums = "".join(str(i) for i in seq)
a = missing_number(nums)
assert  a == missing, "{} {} {} {}".format(a, missing, nums, seq)
```
5. Francesco said

Taking the list comprehension joke too far (I tried something idiomatic ad failed):

```f t = head \$ [a | a <- [1..99999], b <- [1..length t-1], c <- [1..5],
iS (let (x,y) = splitAt b t in x++show a++y) (read . take c \$ t :: Int)]
iS t i = and \$ zipWith (==) t (concatMap show [i..])
```
```λ> f "596597598600601602"
599
λ> f "9111213"
10
```
6. Jussi Piitulainen said

I’m kind of pleased with this one. (Python.)

```def s(diginit, w):
m, k = int(w[:diginit]), 0
while w.startswith(str(m), k): m, k = m + 1, k + len(str(m))
it, at, m = m, k, m + 1
while w.startswith(str(m), k): m, k = m + 1, k + len(str(m))
return at < k and k == len(w) and it

print('expect', 13, 1114, 101, 599)
for w in ('1214', '11131115', '9899100102', '596597598600601602'):
print(s(1, w) or s(2, w) or s(3, w) or s(4, w) or s(5, w))
```
7. kgashok said

@Rutger, for this sequence ”891011121315′, shouldn’t the missing number be 14?

8. Jussi Piitulainen said

Translated my solution to Scheme. The really tricky part turned out to be the auxiliary predicate :/ How many bugs can there be in one line that is not even long? So it turned into three lines and is probably still buggy :)
``` (define (starts-with? s p k)   (let* ((n (string-length s))          (k (min (max 0 k) n)))     (string=? p (substring s k (min n (+ k (string-length p)))))))```

``` (define (prefix s k) (substring s 0 (max 0 (min k (string-length s))))) (define (s diginit w)   (let while ((m (string->number (prefix w diginit))) (k 0))     (if (starts-with? w (number->string m) k)         (while (+ m 1) (+ k (string-length (number->string m))))         (let ((it m) (at k))           (let while ((m (+ m 1)) (k k))             (if (starts-with? w (number->string m) k)                 (while (+ m 1) (+ k (string-length (number->string m))))                 (and (< at k) (= k (string-length w)) it))))))) ```

```(display '(expect 13 1114 101 599)) (newline) (for-each  (lambda (w)    (write (or (s 1 w) (s 2 w) (s 3 w) (s 4 w) (s 5 w)))    (newline))  '("1214" "11131115" "9899100102" "596597598600601602")) ```

9. Mike said

The tricky part was parsing the string of digits into integers. It’s not clear from the problem statement, but I think the string that begins with a single digit number ,e.g., 8, and ends with a triple digit, e.g., 101 would be valid input.

Once the string is parsed into numbers j, j+1, j+2, … j+k, the missing number can be found by calculating the what the sum of j…k should be (sum(1 to k) – sum(1 to j-1)) and subtract the sum of the parsed numbers.

def parse(s, nd):
ns = [int(s[:nd])]
i = nd

while i < len(s):
if s[i-nd] == ‘9’ and s[i] == ‘1’: # identify changed in number of digits per number
nd += 1

n = int(s[i:i+nd])

if ns and not (1 <= n – ns[-1] <= 2): # bail early if numbers aren’t in a valid sequence
return []

ns.append(n)
i += nd

return ns

def missing(s):
for ns in filter(None, (parse(s,nd) for nd in range(1,6))):

if ns[0] + len(ns) == ns[-1]: # check that there is only one missing number

x = (ns[-1]*(ns[-1]+1) – (ns[0]-1)*ns[0])//2 – sum(ns)

if ns[0] < x < ns[-1]: # check that missing number is in the correct range
return x

10. Mike said

Hate it when I do that; here it is with proper formatting:

```def parse(s, nd):
ns = [int(s[:nd])]
i = nd

while i < len(s):
if s[i-nd] == '9' and s[i] == '1':
nd += 1

n = int(s[i:i+nd])

if ns and not (1 <= n - ns[-1] <= 2):
return []

ns.append(n)
i += nd

return ns

def missing(s):
for ns in filter(None, (parse(s,nd) for nd in range(1,6))):
if ns[0] + len(ns) == ns[-1]:
x = (ns[-1]*(ns[-1]+1) - (ns[0]-1)*ns[0])//2 - sum(ns)
if ns[0] < x < ns[-1]:
return x

```
11. haari said

public class MissingNumber {

public static void main(String[] args) {

System.out.println("Enter the number ");
Scanner scanner = new Scanner(System.in);
String numString = scanner.next();

System.out.println("Enter no. of digits");
int numOfDigits = scanner.nextInt();

List<String> list= new ArrayList<String>();
int index = 0;
int n=0;

while (index<numString.length()) {
index=index+numOfDigits;
}
int[] numbers = new int[list.size()];
for(String li:list){
numbers[n]=Integer.parseInt(li);
n++;
}
System.out.println("Missing Numbers are :");
for(int i=0;i<numbers.length;i++){
if(i != numbers.length-1){
if(!(numbers[i]+1 == numbers[i+1])){
System.out.println(numbers[i]+1);
}
}
}
}

}

12. haari said
```public class MissingNumber {

public static void main(String[] args) {

System.out.println("Enter the number ");
Scanner scanner = new Scanner(System.in);
String numString = scanner.next();

System.out.println("Enter no. of digits");
int numOfDigits = scanner.nextInt();

List<String> list= new ArrayList<String>();
int index = 0;
int n=0;

while (index<numString.length()) {
index=index+numOfDigits;
}
int[] numbers = new int[list.size()];
for(String li:list){
numbers[n]=Integer.parseInt(li);
n++;
}
System.out.println("Missing Number is :");
for(int i=0;i<numbers.length;i++){
if(i != numbers.length-1){
if(!(numbers[i]+1 == numbers[i+1])){
System.out.println(numbers[i]+1);
}
}
}
}

}
```
13. Meisam said

def find_missing(num):
i= 1
j = 0
while i < 6 :
Find = True
while j+i 2 or b – a <0:
i += 1
j = 0
Find = False
break
else:
if b – a == 2:
missing_Number = a + 1
j += i
if Find:
print "Missing Number is:",missing_Number
break
find_missing ("596597598600601602")
find_missing ('1234512346123471234912350')

In Python

14. Meisam said
```def find_missing(num):
i= 1
j = 0
while i < 6 :
Find = True
while j+i < len(num):
a = int(num[j:j+i])
b = int(num[j+i:j+i+i])
if b - a > 2 or b - a <0:
i += 1
j = 0
Find = False
break
else:
if b - a == 2:
missing_Number = a + 1
j += i
if Find:
print "Missing Number is:",missing_Number
break
find_missing ("596597598600601602")
find_missing ('1234512346123471234912350')
```

sorry for the previous one
Code is in python

15. mrBrennan said

Hi All, long-time lurker, first-time poster…
This is not in an actual language, just pseudo-code … I hope that’s not against the rules! :-)

– Given:
Input string is <= 200 characters
Numbers are <= 5 digits
All numbers are positive integers
Sequence increases by 1 for adjacent pair EXCEPT
Sequence increases by 2 for exactly one adjacent pair

– Assume:
There are at least two numbers in the input string (otherwise there can't be a 'missing' number)

– Pseudo-code:

set LCC = 1 // L is Length Currently Checking
set FoundIt = false

while LCC <= 5 and FoundIt == false do
{

MightBeThisLengh = True
move to start of input
read LCC characters in to PreviousNumber
read next LCC characters in to CurrentNumber

while (FoundIt = false and MightBeThisLength = true and not end_of_string) do
{

if CurrentNumber == (PreviousNumber + 2)
{
set MissingNumber = PreviousNumber + 1
set FoundIt = True
}
else if CurrentNumber <> (PreviousNumber + 1)
{
// the sequence is broken
set MightBeThisLengh = false
}

set PreviousNumber = CurrentNumber // for next iteration
read next LCC characters in to CurrentNumber

} // end checking this length

LCC ++ // ie increase the length we're currently checking

} // end main while

if FoundIt
{
print MissingNumber
} else {
print 'No such sequence found'
}

16. mrBrennan said

…I tried to wrap this in (sourcecode lang=”java”) and (/sourcecode) (but with square brackets) – didn’t work for some reason…

17. Ha Gia Phat said

C++

int find(string input)
{
int len = input.length();
int j, i, mark = 0;
int ret;
for (i = 1; i <= 5; i++)
{
j = 0;
int flag = 0;
while (j < len – i)
{
int n1, n2;
n1 = atoi(input.substr(j, i).c_str());
n2 = atoi(input.substr(j + i, i).c_str());
if (n2 – n1 != 1)
{
flag++;
mark = j;
}

j += i;
}

if (flag == 1)
{
ret = atoi(input.substr(mark, i).c_str()) + 1;
}
}
return ret;
}

18. yaphats said

Please look at my code, I’m a newbie and trying to learn :D thank you

19. kgashok said

mr Brennan – Your approach is good, but here’s my revision on it:

1 Setup an iteration for len_of_number to go from 1 to 5 (max)
2 Setup an iteration for an index to go from 0 to the length-1 of the sequence

3 Get a current value
4 Get a next value
5 if (next == current + 2) -> Missing number is curr+ 1 ; return this and QUIT
6 if (next == current + 1) -> current Invalid sequence, break and try next len_of_number

Return -1 to indicate FULL sequence or bad sequence

20. mrBrennan said

Hi @kgashok

Your approach is definitely better than mine if we need to confirm whether the entire sequence is valid or not. Mine doesn’t check that.

I was trying for a minimal approach, that would process in the minimum time, assuming we could rely on the numbers being all positive integers and the sequence increasing by one at each number (except the missing number).

Cheers,
Brendan.

21. r. clayton said

A solution in (Racket) Scheme.

22. Not elegant, nor pretty, but reliable :)

string = “989999009901990299049905”

size_results = {}
5.times do |i|
i += 1
size_results[i] = 0
parts = string.scan(/.{#{i}}/).map(&:to_i)
parts.each_with_index do |p, index|
if p + 1 == parts[index + 1]
size_results[i] += 1
end
end
end

result = size_results.sort_by { |k,v| v }.reverse.first
split_into = result.first
parts = string.scan(/.{#{split_into}}/).map(&:to_i)

full = (parts.min .. parts.max).to_a
missing = full – parts
puts “missing: #{missing.first}”

23. Abhay said

C# Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NetPractice
{
class FindTheMissingNumber
{
public static int Slice(string str)
{
//string s;
for (int i = 3; i <=5; i++)
{
int slice_1 = Convert.ToInt32(str.Substring(0, i));
int slice_2 = Convert.ToInt32(str.Substring(i, i));
if ((slice_2 – slice_1 == 1) || (slice_2 – slice_1 == 2))
{
return i;
}
}
return 0;
}
public static string Missing_Number(string str)
{
string sAppend = "";

int length = Slice(str);
int strlength = str.Length;
int j=length;
int num1 = Convert.ToInt32(str.Substring(0, length));
for (int i = 0; i < strlength/length; i++)
{
int num2=0;
if (j != strlength)
{
num2 = Convert.ToInt32(str.Substring(j, length));
j += length;
}

if ((num2 – num1 != 1) && num2 !=0)
sAppend = sAppend+(num1 + 1) + " ";
// return (num1 + 1).ToString();
num1 = num2;
}
return sAppend;
}
/* public static string CompleteString_insert(string str)
{
StringBuilder sb = new StringBuilder(str);
string strInsert = Missing_Number(str).ToString();

}*/

public static void Main()
{
string str = "123412361238123912401242124312451246124712491250";
// string str = "121122123124125126127128129131";
//string str = "555557558560562564566";

//Console.WriteLine("Slice is of length : {0}", Slice(str));
Console.WriteLine("Missing Numbers are :{0} ", Missing_Number(str));
}
}
}

24. Abhay said

C# solution(Valid for 3 and 4 digits)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NetPractice
{
class FindTheMissingNumber
{
public static int Slice(string str)
{
//string s;
for (int i = 3; i <=5; i++)
{
int slice_1 = Convert.ToInt32(str.Substring(0, i));
int slice_2 = Convert.ToInt32(str.Substring(i, i));
if ((slice_2 – slice_1 == 1) || (slice_2 – slice_1 == 2))
{
return i;
}
}
return 0;
}
public static string Missing_Number(string str)
{
string sAppend = "";

int length = Slice(str);
int strlength = str.Length;
int j=length;
int num1 = Convert.ToInt32(str.Substring(0, length));
for (int i = 0; i < strlength/length; i++)
{
int num2=0;
if (j != strlength)
{
num2 = Convert.ToInt32(str.Substring(j, length));
j += length;
}

if ((num2 – num1 != 1) && num2 !=0)
sAppend = sAppend+(num1 + 1) + " ";
// return (num1 + 1).ToString();
num1 = num2;
}
return sAppend;
}
/* public static string CompleteString_insert(string str)
{
StringBuilder sb = new StringBuilder(str);
string strInsert = Missing_Number(str).ToString();

}*/

public static void Main()
{
string str = "123412361238123912401242124312451246124712491250";
// string str = "121122123124125126127128129131";
//string str = "555557558560562564566";

//Console.WriteLine("Slice is of length : {0}", Slice(str));
Console.WriteLine("Missing Numbers are :{0} ", Missing_Number(str));
}
}
}

25. Samir said

26. Atif Farooq said

My C++ Solution

//_______________________________________________________________________
#include
using namespace std;
//_______________________________________________________________________
//Function to input String from the user.

void Arrinp (char Arr [] , int Size)

{
cout<<"\tPlease specify the String = ";
cin.getline (Arr , Size);
cout<=0)

{
NumBucket = NumBucket + (static_cast(Arr[StartIndex])-ASCISUB)*pow (10.0,LoopCount);
StartIndex++;
LoopCount–;
}

return NumBucket;
}
//_______________________________________________________________________
//Function to Assess Arithematic progression on Array.

bool ProgAssessment (char Arr [] , int Digitcount)

{

int Num1 = 0;
int Num2 = 0 ;
int Num3 = 0 ;

switch (Digitcount)

{
case (1):
{
Num1 = CreateNum (Arr ,0, 1);
Num2 = CreateNum (Arr ,1, 1);
Num3 = CreateNum (Arr ,2, 1);
break;
}
case (2):
{
Num1 = CreateNum (Arr ,0, 2);
Num2 = CreateNum (Arr ,2, 2);
Num3 = CreateNum (Arr ,4, 2);
break;
}
case (3):
{
Num1 = CreateNum (Arr ,0, 3);
Num2 = CreateNum (Arr ,3, 3);
Num3 = CreateNum (Arr ,6, 3);
break;
}
case (4):
{
Num1 = CreateNum (Arr ,0, 4);
Num2 = CreateNum (Arr ,4, 4);
Num3 = CreateNum (Arr ,8, 4);
break;
}
case (5):
{
Num1 = CreateNum (Arr ,0, 5);
Num2 = CreateNum (Arr ,5, 5);
Num3 = CreateNum (Arr ,10, 5);
break;
}
}
if ( (Num2 – Num1 ) == 1 || (Num3 – Num1 ) == 2 )

{

return true;

}

else return false;
}
//_______________________________________________________________________
//Function to determine how many Digits constitute Arithematic Progression.

int APDigit (char Arr [])

{

bool ProgressionHypothesis = false;
int DigitConjecture = 0;

while (ProgressionHypothesis != true)

{
DigitConjecture++;
ProgressionHypothesis = ProgAssessment (Arr,DigitConjecture);
}

return DigitConjecture;
}
//_______________________________________________________________________
//Function to Compute Missing Number Based on Findings of APDigit.

int FindMissingNum (char Arr [])

{

int DigitCount = APDigit(Arr);
int SearchIndex = DigitCount;
int Previous = CreateNum(Arr,0,DigitCount);
int Current = CreateNum(Arr,SearchIndex,DigitCount);
bool NumberFound = false;
int MissingNum;

while (!NumberFound)

{
if ( Current-Previous == 2)
{
MissingNum = Current-1;
NumberFound = true;
}
Previous = Current;
SearchIndex = SearchIndex + DigitCount;
Current = CreateNum(Arr,SearchIndex,DigitCount);
}

return MissingNum;
}
//_______________________________________________________________________

void Solution ()

{

char Arr [200];
int MissingNumber;

cout<<"\t________________________________________________________________\n\n";

Arrinp (Arr,200);
MissingNumber = FindMissingNum (Arr);
cout<<"\tMissing Number = "<<MissingNumber<<"\n\n";

cout<<"\t________________________________________________________________\n\n\t";
}
//_______________________________________________________________________

void main()

{
Solution();
}
//_______________________________________________________________________

27. Atif Farooq said

Its almost embarrasing having to share the same code twice Solution should work for 5 digits
//_______________________________________________________________________
#include
using namespace std;
//_______________________________________________________________________
//Function to input String from the user.

void Arrinp (char Arr [] , int Size)

{
cout<<"\tPlease specify the String = ";
cin.getline (Arr , Size);
cout<=0)

{
NumBucket = NumBucket + (static_cast(Arr[StartIndex])-ASCISUB)*pow (10.0,LoopCount);
StartIndex++;
LoopCount–;
}

return NumBucket;
}
//_______________________________________________________________________
//Function to Assess Arithematic progression on Array.

bool ProgAssessment (char Arr [] , int Digitcount)

{

int Num1 = 0;
int Num2 = 0 ;
int Num3 = 0 ;

switch (Digitcount)

{
case (1):
{
Num1 = CreateNum (Arr ,0, 1);
Num2 = CreateNum (Arr ,1, 1);
Num3 = CreateNum (Arr ,2, 1);
break;
}
case (2):
{
Num1 = CreateNum (Arr ,0, 2);
Num2 = CreateNum (Arr ,2, 2);
Num3 = CreateNum (Arr ,4, 2);
break;
}
case (3):
{
Num1 = CreateNum (Arr ,0, 3);
Num2 = CreateNum (Arr ,3, 3);
Num3 = CreateNum (Arr ,6, 3);
break;
}
case (4):
{
Num1 = CreateNum (Arr ,0, 4);
Num2 = CreateNum (Arr ,4, 4);
Num3 = CreateNum (Arr ,8, 4);
break;
}
case (5):
{
Num1 = CreateNum (Arr ,0, 5);
Num2 = CreateNum (Arr ,5, 5);
Num3 = CreateNum (Arr ,10, 5);
break;
}
}
if ( (Num2 – Num1 ) >= 1 && (Num3 – Num1 ) >= 2 )

{
return true;
}

else return false;
}
//_______________________________________________________________________
//Function to determine how many Digits constitute Arithematic Progression.

int APDigit (char Arr [])

{

bool ProgressionHypothesis = false;
int DigitConjecture = 0;

while (ProgressionHypothesis != true)

{
DigitConjecture++;
ProgressionHypothesis = ProgAssessment (Arr,DigitConjecture);
}

return DigitConjecture;
}
//_______________________________________________________________________
//Function to Compute Missing Number Based on Findings of APDigit.

int FindMissingNum (char Arr [])

{

int DigitCount = APDigit(Arr);
int SearchIndex = DigitCount;
int Previous = CreateNum(Arr,0,DigitCount);
int Current = CreateNum(Arr,SearchIndex,DigitCount);
bool NumberFound = false;
int MissingNum;

while (!NumberFound)

{
if ( Current-Previous == 2)
{
MissingNum = Current-1;
NumberFound = true;
}
Previous = Current;
SearchIndex = SearchIndex + DigitCount;
Current = CreateNum(Arr,SearchIndex,DigitCount);
}

return MissingNum;
}
//_______________________________________________________________________

void Solution ()

{

system(“color 05”);

char Arr [200];
int MissingNumber;

cout<<"\n\n\n\tMISSING NUMBER \n\n";

cout<<"\t________________________________________________________________\n\n";

Arrinp (Arr,200);
MissingNumber = FindMissingNum (Arr);
cout<<"\tMissing Number = "<<MissingNumber<<"\n\n";

cout<<"\t________________________________________________________________\n\n\t";
}
//_______________________________________________________________________

void main()

{
Solution();
}
//_______________________________________________________________________