The challenge
You are given a string of numbers in sequence and your task will be to return the missing number. If there is no number missing or there is an error in the sequence, return -1.
For example:
missing("123567") = 4
missing("899091939495") = 92
missing("9899101102") = 100
missing("599600601602") = -1 -- no number missing
missing("8990919395") = -1 -- error in sequence. Both 92 and 94 missing.
The sequence will always be in ascending order.
The solution in Java code
Option 1:
public class Solution {
public static int missing(String s) {
int len = s.length();
if (len == 0 || s.charAt(0) == '0')
return -1;
outer:
for (int k = 1, maxK = Math.min(9, len / 2); k <= maxK; k++) {
int n = Integer.parseInt(s.substring(0, k));
int x = 0;
int i = k;
while (i < len) {
String ns = Integer.toString(++n);
if (s.startsWith(ns, i))
i += ns.length();
else if (x > 0)
continue outer;
else
x = n;
}
if (x > 0 && i == len)
return x;
}
return -1;
}
}
Option 2:
class Solution{
public static int missing(String s){
int res = 0, limit = Math.min(8,s.length()/2);
for (int c = 1; c < limit; ++c) {
int temp = 1;
int m = Integer.parseInt(s.substring(0, c));
int hold = c;
while (hold < s.length()) {
m++;
String n = String.valueOf(m);
if (!n.equals(s.substring(hold, hold+n.length()))) {
res = m;
temp--;
if (temp < 0) break;
}
else hold += n.length();
}
if (temp == 0 && hold == s.length()) return (int)res;
}
return -1;
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
public class SolutionTest{
@Test
public void basicTests(){
assertEquals(4,Solution.missing("123567"));
assertEquals(92,Solution.missing("899091939495"));
assertEquals(100,Solution.missing("9899101102"));
assertEquals(-1,Solution.missing("599600601602"));
assertEquals(-1,Solution.missing("8990919395"));
assertEquals(1002,Solution.missing("998999100010011003"));
assertEquals(10000,Solution.missing("99991000110002"));
assertEquals(-1,Solution.missing("979899100101102"));
assertEquals(900003,Solution.missing("900001900002900004900005900006"));
}
}
Additional test cases
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.*;
public class SolutionTest{
private static Random random = new Random();
private static int asg(String s){
int res = 0, limit = Math.min(8,s.length()/2);
for (int c = 1; c < limit; ++c) {
int temp = 1;
int m = Integer.parseInt(s.substring(0, c));
int hold = c;
while (hold < s.length()) {
m++;
String n = String.valueOf(m);
if (!n.equals(s.substring(hold, hold+n.length()))) {
res = m;
temp--;
if (temp < 0) break;
}
else hold += n.length();
}
if (temp == 0 && hold == s.length()) return (int)res;
}
return -1;
}
private static int random(int l, int u){
return random.nextInt(u-l)+l;
}
@Test
public void basicTests(){
assertEquals(4,Solution.missing("123567"));
assertEquals(92,Solution.missing("899091939495"));
assertEquals(100,Solution.missing("9899101102"));
assertEquals(-1,Solution.missing("599600601602"));
assertEquals(-1,Solution.missing("8990919395"));
assertEquals(1002,Solution.missing("998999100010011003"));
assertEquals(10000,Solution.missing("99991000110002"));
assertEquals(-1,Solution.missing("979899100101102"));
assertEquals(900003,Solution.missing("900001900002900004900005900006"));
}
@Test
public void randomTests(){
for (int i = 0; i < 100; i++) {
int len = random(8,12);
ArrayList <Integer> arr1 = new ArrayList<>();
ArrayList <Integer> arr2 = new ArrayList<>();
int seq = random(1,975000);
arr1.add(seq);
int edge = random(2,5);
int num = (int)Math.pow(10, edge);
int seq2 = num - len + 2;
arr2.add(seq2);
for (int j = 0; j <= len; j++) {
seq++;
seq2++;
arr1.add(seq);
arr2.add(seq2);
}
int trap = random(0,20);
String test1 = "", test2 = "";
int exp1, exp2;
if (trap > 7) {
arr1.remove(random(1,arr1.size()-1));
arr2.remove(random(1,arr2.size()-1));
int checker = random(0,20);
if (checker < 5) {
if (arr1.get(1) % 2 == 0)
arr1.remove(random(1,arr1.size()-1));
else
arr2.remove(random(1,arr2.size()-1));
}
for (int e : arr1)
test1 += String.valueOf(e);
for (int e : arr2)
test2 += String.valueOf(e);
exp1 = asg(test1);
exp2 = asg(test2);
assertEquals(exp1,Solution.missing(test1));
assertEquals(exp2,Solution.missing(test2));
} else {
for (int e : arr1)
test1 += String.valueOf(e);
for (int e : arr2)
test2 += String.valueOf(e);
exp1 = asg(test1);
exp2 = asg(test2);
assertEquals(exp1,Solution.missing(test1));
assertEquals(exp2,Solution.missing(test2));
}
}
}
}
