Simple number sequence in Java

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));
            }   
        
        } 
    }
}
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments