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.
Programming Praxis 
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.
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)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..])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))@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:
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 xpublic 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);
}
}
}
}
}
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 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); } } } } }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
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
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();
}
//_______________________________________________________________________