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.
Code language: JavaScript (javascript)

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; } }
Code language: Java (java)

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; } }
Code language: Java (java)

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")); } }
Code language: Java (java)

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