Can somebody tell an algorithm for finding the smallest missing number in the list.
numList is a java list having numbers like
7896890003
7896890002
7896890000
Here the result should be 7896890001
list is allways in decending order.
The first 6 numbers of each number in the list are same which is "789689"
Iterator it = numList.iterator();
while (it.hasNext()) {
?
}
It should look like this
int previous;
Iterator it = numList.iterator();
if (it.hasNext()) {
int missing = 0;
previous = it.next();
while(it.hasNext()) {
int current = it.next();
if (previous - current > 1)
missing = current + 1;
}
if (missing != 0)
System.out.println("Smallest missing is " + missing);
else
System.out.println("No number missing");
} else {
System.out.println("Empty list");
}
It would be faster if you could traverse the list in reverse order and stop after you find the first missing.
Thanks for posting the algorithm,
one thing which i noticed was that
var
previous=it.next();
gives compilation error saying that incompatible type
found: java.lang.Object
required: int
changing it to
previous = Integer.parseInt(it.next().toString());
helps.
> It would be faster if you could traverse the list in
> reverse order and stop after you find the first
> missing.
if (numList.size < 1) return 7896890000;
ListIterator it = numList.listIterator(numList.size() - 1);
int previous = 7896889999;
while (it.hasPrevious()) {
int num = Integer.parseInt((String) it.previous());
if (num - previous > 1) return previous + 1;
previous = num;
}
return previous + 1;
> If you had an array or other type of RandomAccess,
> you could even use a binary search.
I'll elaborate on that. If you did have an array, then you would have the value at the last index position, which would be the smallest value. You could then sample the middle of the array. You know what the middle value should be.
If the actual number is different, then you know between [n/2, n) there is a number missing. Then you could sample (n + n/2) /2 aand do the same logic.
If the actual number is the same, then you need to search between [0, n/2) to verify all those numbers are there.
A slight optimation would be to see if any numbers were missing.
if (arr[0] + 1 - arr[n-1]) == n) then no numbers are missing (and no need to search). This assumes the numbers are strictly increasing.