## 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.

Advertisements

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

Quick ugly Python list comprehension inefficient solution.

Prints:

4

599

12348

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

In Python3.

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

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

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

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

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

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

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()) {

list.add(numString.substring(index, Math.min(index+numOfDigits,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);

}

}

}

}

}

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

sorry for the previous one

Code is in python

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'

}

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

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;

}

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

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

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.

A solution in (Racket) Scheme.

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

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

Console.ReadKey();

}

}

}

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

Console.ReadKey();

}

}

}

Reblogged this on Muhammad Samir.

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();

}

//_______________________________________________________________________

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();

}

//_______________________________________________________________________