Find The Missing Number

June 26, 2015

Today’s exercise is a tricky little homework problem:

Given a string consisting only of digits, find the missing number. For instance, given the string 596597598600601602 the missing number is 599. You may assume all the numbers are positive integers and the sequence increases by one at each number except the missing number. The numbers will have no more than five digits and the string will have no more than two hundred characters.

Your task is to write a program to find the missing number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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();
}
//_______________________________________________________________________