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