Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
@Cyber Phenix almost correct
@avikodak you cannot check by comparing only first two numbers... the second number could be itself missing or part of a bigger number...
The problem can be divided into 2 parts... finding the number sequence and then finding the missing number in that sequence
Guess the number of digits for the first number by reading numbers from the string one by one. If the previous number you have read is x, the next number must be either x + 1 or x + 2. If it is x + 2, remember x + 1 as the missed number, continue until the end of the string anyway to verify that the initial guess was correct. If you read something else than x + 1 or x + 2, the initial guess was wrong and you need to restart with (next) guess.
For example:
9899100101103104105
First guess length 1
read 9
the next number should be either 10 or 11. Read the next two digits, you get 89.
That is incorrect, so the initial guess was wrong.
Second guess length 2
read 98
the next number should be either 99 or 100. Read the next two digits for 99
the next number should be either 100 or 101. Read the next three digits for 100
... 101
... 103 (remember 102 as the missed number)
... 104
... 105
end of input
Guess of length 2 was verified as correct guess and 102 reported as missing number.
stackoverflow.com/questions/19245137/find-the-missing-number-in-a-given-string
This is my version in java, hopefully this can be improved.
1234567810
12345678911
909192939496979899
100011000210004
121314121316
9899100102103
Program goes like this
package org.manojpotluri.stringmanipulations;
import java.util.HashMap;
import java.util.Map;
public class NumberofDigits {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "1213141517";
Map<Integer, Boolean> resultsMap = new HashMap<Integer, Boolean>();
int startDigit = 0;
boolean result;
for (int i = 1; i<5; i++) {
result = identifyFUnction(str,0,i);
if (result) {
//System.out.println("The starting number of the string is a "+i+ " digit number");
startDigit = i;
resultsMap.put(i, result);
}
resultsMap.put(i, result);
}
//System.out.println(resultsMap);
findMissingNumber(str,startDigit);
}
public static void findMissingNumber(String str, int startDigit){
int start = Integer.parseInt(str.substring(0, startDigit));
int nextnumber1 = start + 1;
int nextnumber2 = start + 2;
/*System.out.println(start);
System.out.println(nextnumber1);
System.out.println(nextnumber2);
System.out.println(next);
System.out.println("---------");*/
if (str.substring(startDigit, str.length()).startsWith(String.valueOf(nextnumber1)) ) {
findMissingNumber(str.substring(startDigit, str.length()), String.valueOf(nextnumber1).length());
}
else if (str.substring(startDigit, str.length()).startsWith(String.valueOf(nextnumber2)) ) {
System.out.println("Missing number in the above sequence is " +nextnumber1);
}
}
public static boolean identifyFUnction(String str, int beginIndex, int offSet) {
int start = Integer.parseInt(str.substring(beginIndex, offSet));
int nextnumber1 = start + 1;
int nextnumber2 = start + 2;
String str2 = str.substring(offSet, str.length());
if (str2.startsWith(nextnumber1+"") || str2.startsWith(nextnumber2+"")) {
return true;
}
else {
return false;
}
}
}
The problem has two parts:
1. Identify the first number (number of digits it must have)
2. Using Arithmetic Progression find the missing number.
For 1.
i)Convert String into an array of single digit integers, "r". Set start_number as r[0]
ii) Iterate through array and check following:
1. If r[i+1] - r[1]== 1 go ahead and increment sum with this element
2. else if r[i+1] - r[i]<0 || r[i+1] - r[i] >2
Go to step i) and reform with next group of digits, i.e. if you had broken down strings with group of one digit, increment this grouping logic to 2 and so on. Reset sum variable to 0.
Missing number(if sequence is correct) = (r[0] + n(n-1)/2 ) - sum
where n is the length of array r.
in that case missing number will be 0. yes that should be additional check. Please correct me if i am missing something.
This approach would not work for '99100101103' where some numbers are 2 digit and others 3 digits.
public static void main(String[] args) {
String s = "98991009899102";
int missingNum = -1;
for (int startLen = 1; startLen <= s.length() / 2 && missingNum == -1; startLen++) {
int prevNum = getInt(s, 0, startLen);
int offset = startLen;
while (true) {
int nextA = prevNum + 1;
int lenA = intLen(nextA);
int nextB = prevNum + 2;
int lenB = intLen(nextB);
//check +1
if (offset + lenA > s.length()) {
missingNum = -1;
break; //wrong sequence
}
int gotNum = getInt(s, offset, lenA);
if (gotNum == nextA) {
prevNum = nextA;
offset += lenA;
if (offset == s.length()) break; // found
continue;
}
if (missingNum != -1) {
missingNum = -1;
break; //wrong sequence
}
//check +2
if (offset + lenB > s.length()) {
missingNum = -1;
break; //wrong sequence
}
gotNum = getInt(s, offset, lenB);
if (gotNum == nextB) {
prevNum = nextB;
offset += lenB;
missingNum = nextA;
if (offset == s.length()) break; // found
continue;
}
missingNum = -1;
break; //wrong sequence
}
}
System.out.print("" + missingNum);
}
private static int getInt(String s, int off, int len) {
String num = s.substring(off, off+len);
return Integer.parseInt(num);
}
private static int intLen(int num) {
int len = 0;
while (num> 0){
num /= 10;
len++;
}
return len;
}
Working for string like 1245,9101213,9899101102
private string FindMissing(string list)
{
int missing = -1;
for (int i = 1; i < (list.Length / 2+1); i++)
{
int first =Convert.ToInt32(list.Substring(0, i));
int pre = first;
int startIndex=i;
while (startIndex<list.Length-i)
{
string temp = list.Substring(startIndex, (pre + 1).ToString().Length);
int diff = Convert.ToInt32(temp) - (pre + 1);
if (diff == 0)
{
startIndex = startIndex + (pre + 1).ToString().Length;
pre = pre + 1;
continue;
}
else if (diff == 1)
{
if (missing != -1)
{
missing = -1;
break;
}
else
{
missing = pre + 1;
pre = pre + 1;
continue;
}
}
else
{
missing = -1;
break;
}
}
if (missing != -1)
break;
}
if (missing == -1)
return "Either it is not a sequence or no number missing";
else
return missing.ToString();
}
private string FindMissing(string list)
{
int missing = -1;
for (int i = 1; i < (list.Length / 2+1); i++)
{
int first =Convert.ToInt32(list.Substring(0, i));
int pre = first;
int startIndex=i;
while (startIndex<list.Length-i)
{
string temp = list.Substring(startIndex, (pre + 1).ToString().Length);
int diff = Convert.ToInt32(temp) - (pre + 1);
if (diff == 0)
{
startIndex = startIndex + (pre + 1).ToString().Length;
pre = pre + 1;
continue;
}
else if (diff == 1)
{
if (missing != -1)
{
missing = -1;
break;
}
else
{
missing = pre + 1;
pre = pre + 1;
continue;
}
}
else
{
missing = -1;
break;
}
}
if (missing != -1)
break;
}
if (missing == -1)
return "Either it is not a sequence or no number missing";
else
return missing.ToString();
}
Code :
int getMissing(BufferedReader br) {
StringTokenizer st = new StringTokenizer(br.readLine());
int sum = 0;
int count = 1;
int min = Integer.parseInt(st.nextToken());
int max = Integer.parseInt(st.nextToken());
sum += min;
count++;
while(st.hasMoreTokens()) {
int num = Integer.parseInt(st.nextToken());
sum += num;
if(min > num)
min = num;
else if(max < num)
max = num;
count++;
}
//Using min*n+(N-1)(N)/2 == sum
int missing = min*count + (count-1)*count/2 - sum;
return missing;
}
I thought the nos. are separated by a space. If thy are continuously arranged, then this approach doesn't work.
In that case:
We would need to :
a. Make a guess on no. of digits in the starting no.
b. Start traversing the string with your assumption. If the current no. is x, then at any point next no. should b either x+1 or x+2(in case the next no. is missing and counter is 0). If say it is x+2 and counter is 0, increment counter. If counter is already 1 then discard this digit guess , go to step a and assume digit count one greater than previous.
c. If you are able to reach the last of string successfully for a particular digit count, print x+1 for the point where we incremented the counter. If for no digit count <= n/2 (length of string are we able to find a successful digit count, then either return the number before first or after last)
Code :
int getMissing(String input) {
int n = input.length();
int missing = -1;
for(int digitCount = 1; digitCount <= n/2; digitCount++) {
int count = 0;
int x = Integer.parseInt(input.substring(digitCount));
int start = x;
missing = start-100;
int i = digitCount;
while(i < n) {
String next = Integer.toString(x+1);
if(input.substring(i, next.length()+i).equals(next)) {
x++;
i += next.length();
}
else {
String nextNext = Integer.toString(x+2);
if(input.substring(i, nextNext.length()+i).equals(nextNext)) {
if(count == 0) {
count++;
missing = x+1;
x += 2;
i += nextNext.length();
}
else
break;
}
else
break;
}
}
if(i == n) {
if(missing == start-100)
return start-1;
else
return missing;
}
}
//Assuming NOT_POSSIBLE is a value to indicate that no missing value possible
return NOT_POSSIBLE;
}
public static int missingNumber(String str)
{
int result = 0;
int maxBaseLimit = (int) Math.floor(str.length()/3);
int count;
for(count = 1; count <= maxBaseLimit; count++)
{
String start = str.substring(0, count);
int index = count;
while(true && index < str.length())
{
int next = Integer.valueOf(start) + 1;
int nextNumberLength = Integer.toString(next).length();
if(index + nextNumberLength > str.length())
{
break;
}
String nextStr = str.substring(index, index + nextNumberLength);
if(next == Integer.valueOf(nextStr))
{
index += nextNumberLength;
start = nextStr;
continue;
}
else if(next+1 == Integer.valueOf(nextStr))
{
result = next;
int acutalNext = next + 1;
index += Integer.toString(acutalNext).length();
start = Integer.toString(acutalNext);
continue;
}
else
{
break;
}
}
}
return result;
}
Tested with the following set of Values
1234567810
12345678911
909192939496979899
100011000210004
121314121316
9899100102103
Program goes like this
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
char * substr(char *mainstr, char *location, int n)
{
int ctr;
for(ctr=0;ctr<n;ctr++)
*(location+ctr) = *(mainstr+ctr);
*(location+ctr) = NULL;
return location;
}
void main(void)
{
long int prevnum,next_num,missingnum=-1;
char ctr, num, digits_altered=0;
char numstr[] = "1234567812345680",substring[10];
clrscr();
for(ctr = 1; ctr <= strlen(numstr) && missingnum ==-1 ; ctr++) {
digits_altered = 0;
num=0;
prevnum = atol( substr(numstr, substring, ctr));
while(1) // Assuming that there are no errors in the Input
{
if(prevnum==(pow(10,ctr)-1)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr+1));
if(prevnum+2==next_num) {
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else if(prevnum+1==next_num){
prevnum=next_num;
ctr++;
}
else
break;
}
else if(prevnum==(pow(10,ctr)-2)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else {
next_num = atol( substr(numstr+num, substring, ctr+1));
if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else break;
}
}
else{
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
}
else break;
}
}
}
gotoxy(30,12);
printf("Missing number is %ld\n", missingnum);
getch();
}
Tested with the following set of Values
1234567810
12345678911
909192939496979899
100011000210004
121314121316
9899100102103
Program goes like this
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
char * substr(char *mainstr, char *location, int n)
{
int ctr;
for(ctr=0;ctr<n;ctr++)
*(location+ctr) = *(mainstr+ctr);
*(location+ctr) = NULL;
return location;
}
void main(void)
{
long int prevnum,next_num,missingnum=-1;
char ctr, num, digits_altered=0;
char numstr[] = "1234567812345680",substring[10];
clrscr();
for(ctr = 1; ctr <= strlen(numstr) && missingnum ==-1 ; ctr++) {
digits_altered = 0;
num=0;
prevnum = atol( substr(numstr, substring, ctr));
while(1) // Assuming that there are no errors in the Input
{
if(prevnum==(pow(10,ctr)-1)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr+1));
if(prevnum+2==next_num) {
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else if(prevnum+1==next_num){
prevnum=next_num;
ctr++;
}
else
break;
}
else if(prevnum==(pow(10,ctr)-2)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else {
next_num = atol( substr(numstr+num, substring, ctr+1));
if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else break;
}
}
else{
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
}
else break;
}
}
}
gotoxy(30,12);
printf("Missing number is %ld\n", missingnum);
getch();
}
Tested with the following set of Values
1234567810
12345678911
909192939496979899
100011000210004
121314121316
9899100102103
Program goes like this
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
char * substr(char *mainstr, char *location, int n)
{
int ctr;
for(ctr=0;ctr<n;ctr++)
*(location+ctr) = *(mainstr+ctr);
*(location+ctr) = NULL;
return location;
}
void main(void)
{
long int prevnum,next_num,missingnum=-1;
char ctr, num, digits_altered=0;
char numstr[] = "1234567812345680",substring[10];
clrscr();
for(ctr = 1; ctr <= strlen(numstr) && missingnum ==-1 ; ctr++) {
digits_altered = 0;
num=0;
prevnum = atol( substr(numstr, substring, ctr));
while(1) // Assuming that there are no errors in the Input
{
if(prevnum==(pow(10,ctr)-1)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr+1));
if(prevnum+2==next_num) {
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else if(prevnum+1==next_num){
prevnum=next_num;
ctr++;
}
else
break;
}
else if(prevnum==(pow(10,ctr)-2)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else {
next_num = atol( substr(numstr+num, substring, ctr+1));
if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else break;
}
}
else{
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
}
else break;
}
}
}
gotoxy(30,12);
printf("Missing number is %ld\n", missingnum);
getch();
}
Tested with the following set of Values
1234567810
12345678911
909192939496979899
100011000210004
121314121316
9899100102103
Program goes like this
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
char * substr(char *mainstr, char *location, int n)
{
int ctr;
for(ctr=0;ctr<n;ctr++)
*(location+ctr) = *(mainstr+ctr);
*(location+ctr) = NULL;
return location;
}
void main(void)
{
long int prevnum,next_num,missingnum=-1;
char ctr, num, digits_altered=0;
char numstr[] = "1234567812345680",substring[10];
clrscr();
for(ctr = 1; ctr <= strlen(numstr) && missingnum ==-1 ; ctr++) {
digits_altered = 0;
num=0;
prevnum = atol( substr(numstr, substring, ctr));
while(1) // Assuming that there are no errors in the Input
{
if(prevnum==(pow(10,ctr)-1)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr+1));
if(prevnum+2==next_num) {
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else if(prevnum+1==next_num){
prevnum=next_num;
ctr++;
}
else
break;
}
else if(prevnum==(pow(10,ctr)-2)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else {
next_num = atol( substr(numstr+num, substring, ctr+1));
if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else break;
}
}
else{
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
}
else break;
}
}
}
gotoxy(30,12);
printf("Missing number is %ld\n", missingnum);
getch();
}
#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;
int getNext(unsigned int start, int unsigned gap, string a){
if(a.length()>= start+gap){
return atoi((a.substr(start, gap)).c_str());
}
return -1;
}
int maxNumInGap(int gap){
int res = 9;
for (int i = 1; i < gap; ++i) {
res = res*10+9;
}
return res;
}
int getMissingNum(int gap, string a){
int first = getNext(0, gap, a);
int start = gap;
if(first == maxNumInGap(gap)){
gap++;
}
int second = getNext(start, gap, a);
while(first != -1 && second != -1 && first == second - 1){
first = second;
start += gap;
if(first == maxNumInGap(gap)){
gap++;
}
second = getNext(start, gap, a);
}
if(first == maxNumInGap(gap)-1){
second = getNext(start, gap+1, a);
}
if(first == second - 2){
return first+1;
}
return -1;
}
int main(int argc, char **argv) {
string a = "9899100101103104105";
int res = -1;
unsigned int gap = 1;
while(res == -1 && gap<a.length())
{
res = getMissingNum(gap++,a);
}
cout << res;
}
This is the complete solution that covered all use cases:
package org.ajeet.algorithms.sequence;
public final class NumbersSequence {
private static int numDigits(String seq){
int digits = 1;
int position =0;
int requiredSuccessAttampts = seq.length() - 2;
int success = 0;
boolean hasTwoTypesNumbers = false;
for(int i=0; i < seq.length(); i++){
int diff = 1; // Because the numbers are in sequence order so diff should be 1.
int failures = 0; // If failures are three than move to next iteration
// We need at least two success
boolean oldsuccess = false;
if(digits != 1){
String sey1 = seq.substring(position, seq.length());
requiredSuccessAttampts = ((sey1.length())/(digits)) + success - 1;
}
for(int j=position; j<=seq.length(); j = j+digits){
if(success >= requiredSuccessAttampts){
System.out.println("This sequence has " + digits + " digit numbers.");
if(hasTwoTypesNumbers){
return --digits;
}
return digits;
}
//If only two numbers are there.
if(seq.length() == digits *2 ){
if(hasTwoTypesNumbers){
return --digits;
}
return digits;
}
String num1Str = seq.substring(j, j+digits);
int num1 = Integer.parseInt(num1Str);
int num2 = Integer.parseInt(seq.substring(j+digits, j+digits+digits));
int tmpDiff = num2 - num1;
//If these are in sequence or a missing number between these two numbers.
if((tmpDiff == diff) || ((num2 == (num1 + 2)) && !(failures > 0))){
++success;
if(success >= requiredSuccessAttampts){
System.out.println("This sequence has " + digits + " digit numbers.");
if(hasTwoTypesNumbers){
return --digits;
}
return digits;
}
} else if((oldsuccess & (num1 != num2) && !(failures > 0)) && (seq.length() >= (j+digits+digits+1))){
//boolean isLastDigit9 = false;
String nextNum = num1+1 + "";
if((num1Str.lastIndexOf("9") == num1Str.length()-1) || (nextNum.lastIndexOf("9") == nextNum.length()-1)){
int num3 = Integer.parseInt(seq.substring(j+digits, j+digits+digits+1));
tmpDiff = num3 - num1;
if(tmpDiff == diff || tmpDiff == diff+1){
position = j+digits;
++digits;
++success;
if(success >= requiredSuccessAttampts){
return --digits;
}
hasTwoTypesNumbers = true;
break;
}
}
} else {
++failures;
if((failures == requiredSuccessAttampts) || (failures == 2)){
System.out.println("This sequence does not contains " + digits + " digit numbers so trying " + (digits + 1) + " digit numbers");
++digits;
success = 0;
hasTwoTypesNumbers = false;
break;
}
}
if(tmpDiff < 0){
++digits;
break;
}
if(tmpDiff == 1){
oldsuccess = true;
}
}
}
return 0;
}
private static int getMissingNumber(String seq, int numdigits){
return getMissingNumber(seq,0, numdigits);
}
private static int getMissingNumber(String seq, int position, int digits){
if(position+digits+digits >= seq.length()+1){
return 0;
}
String num1Str = seq.substring(position, position+digits);
int num1 = Integer.parseInt(num1Str);
int num2 = Integer.parseInt(seq.substring(position+digits, position+digits+digits));
int tmpDiff = num2 - num1;
if(num1Str.lastIndexOf("9") == num1Str.length()-1){
int num3 = Integer.parseInt(seq.substring(position+digits, position+digits+digits+1));
tmpDiff = num3 - num1;
if(tmpDiff == 2){
return num1 +1;
}
position+=digits;
++digits;
return getMissingNumber(seq, position, digits);
}
if (tmpDiff !=0 && tmpDiff != 1){
return (num1 + 1);
}
return getMissingNumber(seq, position+digits, digits);
}
public static int missingNumber(String seq){
int digits = numDigits(seq);
return getMissingNumber(seq, digits);
}
//Test client
public static void main(String[] args) {
String seq = "9899100101103104105";
int digits = numDigits(seq);
//System.out.println(digits);
System.out.println("This is the missing number: " + getMissingNumber(seq, digits));
}
}
You can download its working copy from here: github.com/4ajeet/Algorithms
Suppose you enter the string as 9899100101103104105
(i)suppose first character(9) follow the sequence
which implies next character should be 10 but it is not
(ii)now suppose first two character(98) follow the sequence
next character should be 99(true) ,further next would be 100(true) and so on
(iii) if sequence is break and the difference is 1 ,which implies the missing no.
Code is
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int check_next(int);
int check_digit(int);
int no_of_digit_current_no, no_of_digit_next_no;
int sequence_break_status=0;
void main()
{
clrscr();
char *str=(char*)malloc(100*sizeof(char));
printf("Enter String ");
scanf("%s",str);
int length = strlen(str);
int next_no;
int original_no;
for(int i=0;i<length;i++)
{
int current_no=0;
for(int j=0;j<=i;j++)
{
//generating the current_no
current_no=current_no+(((int)str[j]-48)*pow(10,i-j));
}
original_no=current_no;
next_no=check_next(current_no);
//finding_no_of_digit
no_of_digit_current_no=check_digit(current_no);
no_of_digit_next_no=check_digit(next_no);
int start_index=i+1;
int end_index=start_index+(no_of_digit_next_no-1);
//compare the next_no with string
while(end_index<length)
{
int sum=0;
sequence_break_status=0;
while(start_index<=end_index)
{
sum=sum+((int)(str[start_index]-48))*pow(10,end_index-start_index);
start_index++;
}
if(next_no!=sum)
{
if((sum-next_no)!=1)
{
sequence_break_status=1;
break;
}
else
{
printf("\nmissing no is %d",(next_no));
current_no=sum;
next_no=check_next(current_no);
//finding_no_of_digit
no_of_digit_current_no=check_digit(current_no);
no_of_digit_next_no=check_digit(next_no);
start_index=end_index+1;
end_index=start_index+(no_of_digit_next_no-1);
}
}
else
{
current_no=next_no;
next_no=check_next(current_no);
//finding_no_of_digit
no_of_digit_current_no=check_digit(current_no);
no_of_digit_next_no=check_digit(next_no);
start_index=end_index+1;
end_index=start_index+(no_of_digit_next_no-1);
}
}
if(sequence_break_status==0)
{
printf("\ninitial no is %d ",original_no);
}
}
getch();
}
int check_next(int current_no)
{
int next_no=current_no+1;//no are in sequence
return next_no;
}
int check_digit(int no)
{
int no_of_digit=0;
while(no > 0)
{
no=no/10;
no_of_digit++;
}
return no_of_digit;
}
i would suggest the solution as:
take first i chars from string (i varies from 2 to n)
subtract 1 or 2 from the last char, then the left over string should be having 2 identical strings separated by 0 or by nothing
like(taking only 1 as the element)
4748
so
47=> 46 => no
474 => 473 => no
4748=> 4747 > yes
with this we have to go from 1->n
as the length of int can be n/2 with having sub strings which are also increasing order like
474849505152474849505154
the answer in this case is 474849505153
Tested with 99100101102104
and 12345678911
#include<iostream>
#include<stdio.h>
//#include<math.h>
#include<stdlib.h>
using namespace std;
int counter =0;
int missingNUM=0;
int digitChangeHappened=0;
const char* input="12345678911";
bool checkmissing(int* ,int);
int inline pow(int x,int y)
{
int i;
int ret=1;
for(i=0;i<y;i++)
{
ret *= x;
}
return ret;
}
int main()
{
// int counter =0;
int n=20;
int a[n];
// copying the string
while(*input)
{
//cout<<"the element is :"<<(*input)<<"\t";
a[counter]=(*input)-48;
counter++;
input++;
}
for(int h=0;h<14;h++)
{
cout<<a[h]<<endl;
}
input=input-counter;
cout<<"the starting num is :"<<(*input)<<endl;
for(int j=2; j<counter; j++)
{
int lhs=0;
int rhs=0;
int numChange=1;
int maxNumInNthDigit=0;
if(numChange)
{
if(digitChangeHappened)
{
j--;
}
for(int m=0;m<j;m++)
{
int plhs= j-m;
maxNumInNthDigit=maxNumInNthDigit+9*pow(10,plhs-1);
}
numChange=0;
}
//find hte lhs
for(int k=0; k<j; k++)
{
lhs=lhs+(a[k])*pow(10,j-k-1);
}
if(lhs==maxNumInNthDigit)
{
numChange=1;
digitChangeHappened=1;
++j;
}
for(int k=0; k<j; k++)
{
int powerOften= (j-(k+1));
volatile int powerValue=pow(10,j-k-1);
// cout<<"j="<<j<<"\t k="<<k<<"\t powe="<<powerValue<<endl;
int arraynum=a[k+j-numChange];
rhs=rhs+(powerValue)*(arraynum);
}
if((lhs==(rhs-1))||(lhs==(rhs-2)))
{
bool b=checkmissing( a , (j-digitChangeHappened) );
if(!b)
{
continue;
}
else
{
exit(0);
}
}
else
{
digitChangeHappened=0;
continue;
}
}
cout<<"there is no mising number"<<endl;
}
bool checkmissing(int a[] ,int j)
{
int numChange=1;
int maxNumInNthDigit=0;
// int a[counter];
for(int q=0;q<counter-1;q=q+j-numChange)
{
int lhs=0;
int rhs=0;
if(numChange)
{
//j--;
for(int m=0;m<j;m++)
{
maxNumInNthDigit=maxNumInNthDigit+9*pow(10,j-m-1);
}
numChange=0;
}
//find hte lhs
for(int k=0; k<j; k++)
{
lhs=lhs+(a[q+k])*pow(10,j-k-1);
}
if(lhs==maxNumInNthDigit)
{
numChange=1;
++j;
}
for(int k=0; k<j; k++)
{
rhs=rhs+(a[q+k+j-numChange])*pow(10,j-k-1);
}
if((lhs==(rhs-1)))
{
continue;
}
else if((lhs==(rhs-2)))
{
if(missingNUM)
{
cout<<"mutlple missings so returning "<<endl;
return false;
}
missingNUM=lhs+1;
continue;
}
else if(q==counter-j)
{
if(!missingNUM)
{
cout<<"No Missing number found";
return false;
}
else
{
cout<<"Misisng number is :"<<missingNUM<<"\n";
return true;
}
}
else
{
return false;
}
}
}
I think this can be solved in O(N) time complexity with following approach:
For consideration take this as e.g s[]=1234123512361238
1. In first iteration we will take only 1 chars as a number and iterate through it ,and when we reach the largest digit of that 1 digit number i.e 9 we will increase the iteration rate to +=2 if we will get only 1 alteration then that will be the ans otherwise we will move to next iteration. So here taking 1 chars it works s[4] having only 1 alteration but at s[5] we have 2 alterations so we break.
2. Now we check for numbers of 2 digit lenght from starting, following the above process again. For example here it works till only s[2] but after it has >1 alterations.
3. Similarly we will check for 3 digit..
4. Then for 4 digit... so we get our ans in 4 digit. 1234 1235 1236 1237(miss) 1238 .
Complexity of code will be T(N + N/2 + N/3 +N/4 +N/5 + ....) ~ const*T(N) = O(N) .
Am i right? Correct me where i am wrong.
Thank You.
class MissingNumber {
public static void main(String args[]) {
findMissingNumber();
}
public static void findMissingNumber()
{
// Enter the sequence here
String s = new String("9798100101102");
System.out.println("The sequence is " + s);
int position = -1, digitsInNumber = 0, flagA = 0, flagB = 0;
do {
flagA = 0;
flagB = 0;
digitsInNumber++;
for (int i = 0; (i + digitsInNumber) < s.length(); i += digitsInNumber) {
if ((Integer.parseInt(s.substring(i + digitsInNumber, i + 2 * digitsInNumber))
- Integer.parseInt(s.substring(i, i + digitsInNumber)) == 1)) {
continue;
}
if (Integer.parseInt(s
.substring(i + digitsInNumber, i + 2 * digitsInNumber + 1))
- Integer.parseInt(s.substring(i, i + digitsInNumber)) == 1) {
digitsInNumber++;
i--;
continue;
}
if (Integer.parseInt(s
.substring(i + digitsInNumber, i + 2 * digitsInNumber + 1))
- Integer.parseInt(s.substring(i, i + digitsInNumber)) == 2) {
digitsInNumber++;
position = i;
flagB = 1;
i--;
continue;
}
if (Integer.parseInt(s.substring(i + digitsInNumber, i + 2 * digitsInNumber))
- Integer.parseInt(s.substring(i, i + digitsInNumber)) == 2) {
position = i;
continue;
} else {
flagA = -1;
break;
}
}
} while (flagA < 0);
if (flagB != 1)
System.out.println("The missing number is "
+ (Integer.parseInt(s.substring(position, position + digitsInNumber)) + 1));
else {
digitsInNumber--;
System.out.println("The missing number is "
+ (Integer.parseInt(s.substring(position, position + digitsInNumber)) + 1));
}
}
}
Solution:
* 1. Search through the string one digit at a time and compare consecutive numbers
* as long as the previous number is less than the next number. (Because the numbers are in sequence)
* 2. If num1 < num2 and if the difference between them is 1 then get the missing number by taking their average
* 3. If num1 > num2, there are conditions possible
* a. the number of digits in the sequence is incorrect,
* hence search the string for numbers with (digits + 1) range.
* Eg: If the string is "454647485051", when the num1 = 5 (str[1]) and num2 = 4 (str[2]),
* increment the number of the digits in the numbers to two.
* b. the sequence progressed into next number of digits number.
* So, continue search with (digit + 1) range.
* Eg: If the string is "9899100101103104", the string is of 2 digit range
* but progresses into 3 digits at 100.
*/
int findMissingNumber(string str) {
int digits = 1;
int i = 1;
int num1 = str[0] - '0';
int num2 = 0;
int missing_num = 0;
while (i < str.size()) {
if(i == 0) {
for(int j = 0; j < digits; j++) {
num1 = num1 * 10 + str[j] - '0';
}
i = i + digits;
}
num2 = 0;
for(int k = i; k < (i + digits); k++) {
num2 = num2 * 10 + str[k] - '0';
}
if(num1 < num2) {
if((num2 - num1) != 1) {
missing_num = ((num1 + num2) % 2 == 0) ? (num1 + num2) / 2 : ((num1 + num2) / 2) + 1;
}
i = i + digits;
num1 = num2;
}
else {
num2 = num2 * 10 + str[i + digits] - '0';
digits++;
if((num2 - num1) <= 2) {
i = i + digits;
}
else {
i = 0;
num1 = 0;
}
}
}
return missing_num;
}
idea : in a string of n characters, the a number sequence can be of max n/2 length there has to be a second number to find the missing number....further the length% x = 0 where x are possible options for length of the sequences,this reduces the options to a very small number where Brute force could be applied to check the max sequence possible....please correct me if i have missed out something...
using System;
namespace FindMissingNumber
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Given a string of numbers in sequence order. Find the missing number.");
Console.WriteLine("Enter a string of numbers with one missing number: ");
string s = Console.ReadLine();
int index = 0;
int endIndex = s.Length;
int subStringLength = 1;
int missing = 0;
string first = string.Empty;
string second = string.Empty;
while (index + first.Length < endIndex)
{
if (!string.IsNullOrWhiteSpace(second) && IsAllNine(second))
{
first = GetSubstring(s, index, subStringLength - 1);
}
else
{
first = GetSubstring(s, index, subStringLength);
}
if (IsAllNine(first))
{
second = GetSubstring(s, index + first.Length, first.Length + 1);
}
else
{
second = GetSubstring(s, index + first.Length, first.Length);
}
if (IsInSequence(first, second))
{
index += first.Length;
if (!IsAllNine(second))
{
subStringLength = second.Length;
}
else
{
subStringLength = second.Length + 1;
}
}
else if (IsDifferenceTwo(first, second))
{
missing = Convert.ToInt32(second) - 1;
index += first.Length;
if (!IsAllNine(second))
{
subStringLength = second.Length;
}
else
{
subStringLength = second.Length + 1;
}
}
else
{
index = 0;
subStringLength = first.Length + 1;
}
}
if (missing == 0)
{
Console.WriteLine("There is no missing number in sequence.");
}
else
{
Console.WriteLine("Missling Number: {0}", missing);
}
Console.ReadLine();
}
protected static string GetSubstring(string s, int startIndex, int length)
{
return s.Substring(startIndex, length);
}
protected static bool IsInSequence(string one, string two)
{
bool isInSequence = false;
if (Convert.ToInt32(two) - Convert.ToInt32(one) == 1)
{
isInSequence = true;
}
return isInSequence;
}
protected static bool IsAllNine(string s)
{
bool isAllNine = false;
int number = Convert.ToInt32(s);
int numberDivide = number/9;
if (number % 9 == 0 && ((number / 9).ToString().Length) == s.Length)
{
isAllNine = true;
}
return isAllNine;
}
protected static bool IsDifferenceTwo(string first, string second)
{
bool isDifferenceTwo = false;
if (Convert.ToInt32(second) - Convert.ToInt32(first) == 2)
{
isDifferenceTwo = true;
}
return isDifferenceTwo;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace FindMissingNumber
{
class Program
{
static void Main(string[] args)
{
string numbers = "12345678911";
string missingNumber = null;
int currentIndex = 0;
int nextIndex = 1;
while (currentIndex < numbers.Length)
{
string nextNumber = (int.Parse(numbers.Substring(0, currentIndex + 1)) + 1).ToString();
bool foundMissing = false;
while (nextIndex < numbers.Length)
{
string possibleNextNumber = numbers.Substring(nextIndex, nextNumber.Length);
if (possibleNextNumber.Equals(nextNumber))
{
nextIndex += nextNumber.Length;
nextNumber = (int.Parse(nextNumber) + 1).ToString();
}
else
{
if (!foundMissing)
{
foundMissing = true;
missingNumber = nextNumber;
nextNumber = (int.Parse(nextNumber) + 1).ToString();
}
else
{
foundMissing = false;
missingNumber = null;
break;
}
}
}
if (foundMissing)
break;
currentIndex++;
nextIndex = currentIndex + 1;
}
Console.WriteLine(missingNumber);
Console.ReadLine();
}
}
}
public static int MissingNumber(this string input)
{
int i = 0;
int groupFirst = 1;
try
{
while (i < input.Length)
{
var firstNum = GetNumber(input, i, groupFirst);
int groupSecond = GetOrder(firstNum + 1);
var secondNum = GetNumber(input, i + groupFirst, groupSecond);
if (firstNum < secondNum && (firstNum + 1 == secondNum || firstNum + 2 == secondNum))
{
i += groupFirst;
if (firstNum + 2 == secondNum)
{
return firstNum + 1;
}
groupFirst = groupSecond;
}
else
{
var temp = GetNumber(input, i + groupFirst, groupSecond + 1);
if (firstNum < temp && firstNum + 2 == temp)
{
return firstNum + 1;
}
i = 0;
groupFirst++;
}
}
}
catch (IndexOutOfRangeException)
{
return -1;
}
return i;
}
private static int GetOrder(int number)
{
int order = 0;
while (number > 0)
{
number = number / 10;
order++;
}
return order;
}
private static int GetNumber(string input, int index, int group)
{
double value = 0;
for (int i = group; i > 0; i--)
{
value += Math.Pow(10, i - 1) * (input[index++] - '0');
}
return Convert.ToInt32(value);
}
public static int MissingNumber(this string input)
{
int i = 0;
int groupFirst = 1;
try
{
while (i < input.Length)
{
var firstNum = GetNumber(input, i, groupFirst);
int groupSecond = GetOrder(firstNum + 1);
var secondNum = GetNumber(input, i + groupFirst, groupSecond);
if (firstNum < secondNum && (firstNum + 1 == secondNum || firstNum + 2 == secondNum))
{
i += groupFirst;
if (firstNum + 2 == secondNum)
{
return firstNum + 1;
}
groupFirst = groupSecond;
}
else
{
var temp = GetNumber(input, i + groupFirst, groupSecond + 1);
if (firstNum < temp && firstNum + 2 == temp)
{
return firstNum + 1;
}
i = 0;
groupFirst++;
}
}
}
catch (IndexOutOfRangeException)
{
return -1;
}
return i;
}
private static int GetOrder(int number)
{
int order = 0;
while (number > 0)
{
number = number / 10;
order++;
}
return order;
}
private static int GetNumber(string input, int index, int group)
{
double value = 0;
for (int i = group; i > 0; i--)
{
value += Math.Pow(10, i - 1) * (input[index++] - '0');
}
return Convert.ToInt32(value);
}
I have used a very basic approach which makes the program very simple.
Here are the steps :-
Step 1 :- consider numbers starts with one digit. so, i have passed j=1 along with the string.
Step 2:- traverse through the string and when encounter any number which gives greater length of number after adding 1 ( eg:- 9,99,999,.....) increase j by 1.
Step 3:- if the next number of j length is greater by 2 than current number then current number+1 is missing.
Step 4:- if next number is continuous then continue the traversing.
Step 5:- if next number is neither greater by 2 nor by 1 then you are traversing the string in wrong way considering length j. In that case call the function again and assume the length of the number starts with j++.
step 6:- continue with step 2.
Assumptions:- there are no duplicate numbers and only 1 number is missing.
package String;
class missingnumber
{
public long findmissing(String s,int j)
{
int i=0,a=0,b=j,missing=-1;
while(i<s.length()){
a=Integer.valueOf(s.substring(i, i+j));
i=i+j;
if(i<s.length() && String.valueOf(a+1).length()>String.valueOf(Integer.valueOf(s.substring(i, i+j))).length()){
j++;
}
if(i<s.length() && a+2==Integer.valueOf(s.substring(i, i+j))){
missing=a+1;
}
else if(i<s.length() && a+2!=Integer.valueOf(s.substring(i, i+j)) && a+1!=Integer.valueOf(s.substring(i, i+j)))
return findmissing(s,b+1);
}
return missing;
}
public static void main(String[] arg)
{
String s="789790791792794";
int a=1;
missingnumber m = new missingnumber();
long no=m.findmissing(s,a);
if(no!=-1)
System.out.println("missing term is "+no);
else
System.out.println("Don't have missing number");
}
}
Not exhaustively tested, but here you go. (doesn't work if the missing number is at the end or beginning)
public static void main(String[] args) {
findMissing("9899100101103104105");
findMissing("4567810");
}
public static void findMissing(String s) {
int max = String.valueOf(Integer.MAX_VALUE).length();
for ( int i = 1; i < max; i++ ) {
Integer guess = null;
int value = Integer.parseInt(s.substring(0, i));
for ( int j = i; j < s.length(); ) {
String expected = String.valueOf(value + 1);
int end = Math.min(s.length(), j + expected.length());
String actual = s.substring(j, end);
if ( expected.equals(actual) ) {
value++;
j += expected.length();
} else {
if ( guess == null ) {
guess = Integer.parseInt(expected);
value++;
} else {
guess = null;
break;
}
}
}
if ( guess != null )
System.out.println("Missing number is " + guess);
}
}
public static void findMissingNumber(String input) {
int length = 1;
while (length <= input.length()) {
int i = 0;
String num = input.substring(i, length);
Integer currNum = Integer.parseInt(num);
Integer expectedNextNum = currNum + 1;
Integer expectedNextToNxtNum = expectedNextNum + 1;
int beginIndex = num.length();
int endIndex = beginIndex
+ String.valueOf(expectedNextNum).length();
String nextDigit = input.substring(beginIndex, endIndex);
if (expectedNextNum.equals(Integer.parseInt(nextDigit))) {
// go ahead for third number
beginIndex = endIndex;
endIndex = beginIndex
+ String.valueOf(expectedNextToNxtNum).length();
String nextTonxtDigit = input.substring(beginIndex, endIndex);
if (expectedNextToNxtNum.equals(Integer
.parseInt(nextTonxtDigit))) {
// while loop to identify next consecutive number
identifyMissingNoInIdentifiedSeq(input,
expectedNextToNxtNum, endIndex);
break;
} else {
System.out.println(expectedNextToNxtNum);
break;
}
} else if (expectedNextNum>Integer.parseInt(nextDigit)) {
endIndex = endIndex + 1;
String nextTonxtDigit = input.substring(beginIndex, endIndex);
if (expectedNextToNxtNum.equals(Integer.parseInt(nextTonxtDigit))) {
// missing number is nextNum
System.out.println(expectedNextNum);
break;
} else {
length++;
}
}
else{
length++;
}
}
}
public static void identifyMissingNoInIdentifiedSeq(String input,
Integer num, int startIndex) {
Integer numberToFind = num + 1;
while (true) {
int endIndex = startIndex + (numberToFind + "").length();
String nextTonxtDigit = input.substring(startIndex, endIndex);
if (!numberToFind.equals(Integer.parseInt(nextTonxtDigit))) {
System.out.println(numberToFind);
break;
}
numberToFind++;
startIndex = endIndex;
}
}
public static void findMissingNumber(String input) {
int length = 1;
while (length <= input.length()) {
int i = 0;
String num = input.substring(i, length);
Integer currNum = Integer.parseInt(num);
Integer expectedNextNum = currNum + 1;
Integer expectedNextToNxtNum = expectedNextNum + 1;
int beginIndex = num.length();
int endIndex = beginIndex
+ String.valueOf(expectedNextNum).length();
String nextDigit = input.substring(beginIndex, endIndex);
if (expectedNextNum.equals(Integer.parseInt(nextDigit))) {
// go ahead for third number
beginIndex = endIndex;
endIndex = beginIndex
+ String.valueOf(expectedNextToNxtNum).length();
String nextTonxtDigit = input.substring(beginIndex, endIndex);
if (expectedNextToNxtNum.equals(Integer
.parseInt(nextTonxtDigit))) {
// while loop to identify next consecutive number
identifyMissingNoInIdentifiedSeq(input,
expectedNextToNxtNum, endIndex);
break;
} else {
System.out.println(expectedNextToNxtNum);
break;
}
} else if (expectedNextNum>Integer.parseInt(nextDigit)) {
endIndex = endIndex + 1;
String nextTonxtDigit = input.substring(beginIndex, endIndex);
if (expectedNextToNxtNum.equals(Integer.parseInt(nextTonxtDigit))) {
// missing number is nextNum
System.out.println(expectedNextNum);
break;
} else {
length++;
}
}
else{
length++;
}
}
}
public static void identifyMissingNoInIdentifiedSeq(String input,
Integer num, int startIndex) {
Integer numberToFind = num + 1;
while (true) {
int endIndex = startIndex + (numberToFind + "").length();
String nextTonxtDigit = input.substring(startIndex, endIndex);
if (!numberToFind.equals(Integer.parseInt(nextTonxtDigit))) {
System.out.println(numberToFind);
break;
}
numberToFind++;
startIndex = endIndex;
}
}
#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;
int getNext(unsigned int start, int unsigned gap, string a){
if(a.length()>= start+gap){
return atoi((a.substr(start, gap)).c_str());
}
return -1;
}
int maxNumInGap(int gap){
int res = 9;
for (int i = 1; i < gap; ++i) {
res = res*10+9;
}
return res;
}
int getMissingNum(int gap, string a){
int first = getNext(0, gap, a);
int start = gap;
if(first == maxNumInGap(gap)){
gap++;
}
int second = getNext(start, gap, a);
while(first != -1 && second != -1 && first == second - 1){
first = second;
start += gap;
if(first == maxNumInGap(gap)){
gap++;
}
second = getNext(start, gap, a);
}
if(first == maxNumInGap(gap)-1){
second = getNext(start, gap+1, a);
}
if(first == second - 2){
return first+1;
}
return -1;
}
int main(int argc, char **argv) {
string a = "9899100101103104105";
int res = -1;
unsigned int gap = 1;
while(res == -1 && gap<a.length())
{
res = getMissingNum(gap++,a);
}
cout << res;
}
/**
* Given a string of numbers in sequence order. find the missing number.Range is not given.
* sample input:"9899100101103104105"
* Answer:102
*/
public class Problem3 {
public static void main(String[] args) {
String val = "9899100101103104105";
int valLen = val.length();
int cnt = 0;
int firstNum = Integer.parseInt(val.substring(0, 1));
int valIndex = 1, updtIndex;
int newVal = firstNum + 1;;
int newNoIs = 0, rotateIndex = 1, noToCompare;
while (true) {
for (int i = 1; i < valLen; ) {
updtIndex = valIndex + String.valueOf(newVal).length();
i = i + String.valueOf(newVal).length();
if (i < valLen) {
noToCompare = Integer.parseInt(val.substring(valIndex, updtIndex));
if (newVal == noToCompare) {
cnt++;
} else {
newNoIs = noToCompare-1;
newVal++;
if (newVal == noToCompare) {
cnt++;
}
}
valIndex = updtIndex;
} else
break;
newVal++;
}
if (cnt > 3 && newNoIs != 0) {
System.out.println(newNoIs);
break;
}else {
firstNum = Integer.parseInt(val.substring(0, ++rotateIndex));
newVal = firstNum+1;
valIndex = String.valueOf(firstNum).length() ;
}
}
}
}
/**
* Given a string of numbers in sequence order. find the missing number.Range is not given.
* sample input:"9899100101103104105"
* Answer:102
*/
public class Problem3 {
public static void main(String[] args) {
String val = "9899100101103104105";
int valLen = val.length();
int cnt = 0;
int firstNum = Integer.parseInt(val.substring(0, 1));
int valIndex = 1, updtIndex;
int newVal = firstNum + 1;;
int newNoIs = 0, rotateIndex = 1, noToCompare;
while (true) {
for (int i = 1; i < valLen; ) {
updtIndex = valIndex + String.valueOf(newVal).length();
i = i + String.valueOf(newVal).length();
if (i < valLen) {
noToCompare = Integer.parseInt(val.substring(valIndex, updtIndex));
if (newVal == noToCompare) {
cnt++;
} else {
newNoIs = noToCompare-1;
newVal++;
if (newVal == noToCompare) {
cnt++;
}
}
valIndex = updtIndex;
} else
break;
newVal++;
}
if (cnt > 3 && newNoIs != 0) {
System.out.println(newNoIs);
break;
}else {
firstNum = Integer.parseInt(val.substring(0, ++rotateIndex));
newVal = firstNum+1;
valIndex = String.valueOf(firstNum).length() ;
}
}
}
}
/**
* Given a string of numbers in sequence order. find the missing number.Range is not given.
* sample input:"9899100101103104105"
* Answer:102
*/
public class Problem3 {
public static void main(String[] args) {
String val = "9899100101103104105";
int valLen = val.length();
int cnt = 0;
int firstNum = Integer.parseInt(val.substring(0, 1));
int valIndex = 1, updtIndex;
int newVal = firstNum + 1;
int newNoIs = 0, rotateIndex = 1, noToCompare;
while (true) {
for (int i = 1; i < valLen; ) {
updtIndex = valIndex + String.valueOf(newVal).length();
i = i + String.valueOf(newVal).length();
if (i < valLen) {
noToCompare = Integer.parseInt(val.substring(valIndex, updtIndex));
if (newVal == noToCompare) {
cnt++;
} else {
newNoIs = noToCompare - 1;
newVal++;
if (newVal == noToCompare) {
cnt++;
}
}
valIndex = updtIndex;
} else
break;
newVal++;
}
if (cnt > 3 && newNoIs != 0) {
System.out.println(newNoIs);
break;
} else {
firstNum = Integer.parseInt(val.substring(0, ++rotateIndex));
newVal = firstNum + 1;
valIndex = String.valueOf(firstNum).length();
}
}
}
}
i think ..calculate the sum of all natural numbers in between range ,sum of numbers series in AP (n/2(first+last)).then subtract with sum of value in given array. you will get missing number.
First of all, how do i differentiate one number is ending in that given string. is it comma separated in the string? If yes, then there are other methods also which use XOR of given numbers and XOR of all the numbers from start to end. that will give you the missing number.
Assuming the numbers in the string are ordered
sample input:"9899100101103104105"
Now algo has two steps
1. Finding the delimiters to identify the proper number sequence
2. Once we confirm on sequence it is straight forward to identify the missing number.
Step 1:
Assume sequence of single digit numbers:
1. first number is 9, next expected number is 10, but we found 8
break at this point and parse the string for 2 digit numbers
2. First number is 99, next expected is 99, next expected is 100 ...e.t.c
Now we might confirm on 2 digit sequence
3. After 101 expected is 102 but we found 103, which indicates one look ahead is necessary to confirm on sequence
careful coding of this method can identify multiple missing numbers too ..
public void fill_missing_number(int[] arr) {
ArrayList<Integer> filled = new ArrayList<Integer>();
HashSet<Integer> h= new HashSet<Integer>();
int tmp=0;
for(int i=0;i<arr.length;i++) {
if (!h.contains(arr[i])) {
for(int j=tmp;j<=arr[i];j++) {
filled.add(j);
h.add(j);
}
tmp = arr[i]+1;
}
}
System.out.print("Filled Number:");
for (int num: filled) {
System.out.print(" " + num);
}
}
Tested with the following set of Values
1234567810
12345678911
909192939496979899
100011000210004
121314121316
9899100102103
Program goes like this
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
char * substr(char *mainstr, char *location, int n)
{
int ctr;
for(ctr=0;ctr<n;ctr++)
*(location+ctr) = *(mainstr+ctr);
*(location+ctr) = NULL;
return location;
}
void main(void)
{
long int prevnum,next_num,missingnum=-1;
char ctr, num, digits_altered=0;
char numstr[] = "1234567812345680",substring[10];
clrscr();
for(ctr = 1; ctr <= strlen(numstr) && missingnum ==-1 ; ctr++) {
digits_altered = 0;
num=0;
prevnum = atol( substr(numstr, substring, ctr));
while(1) // Assuming that there are no errors in the Input
{
if(prevnum==(pow(10,ctr)-1)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr+1));
if(prevnum+2==next_num) {
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else if(prevnum+1==next_num){
prevnum=next_num;
ctr++;
}
else
break;
}
else if(prevnum==(pow(10,ctr)-2)) {
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else {
next_num = atol( substr(numstr+num, substring, ctr+1));
if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
ctr++;
}
else break;
}
}
else{
next_num = atol( substr(numstr+(num+=ctr), substring, ctr));
if(next_num==prevnum+1)
prevnum=next_num;
else if(prevnum+2==next_num)
{
missingnum=prevnum+1;
prevnum=next_num;
}
else break;
}
}
}
gotoxy(30,12);
printf("Missing number is %ld\n", missingnum);
getch();
}
Pseudo Code
- Cyber Phoenix August 22, 20131. Read String array and check for the following
2. Check if unit array is sequential, return true if yes else false example 45678 -> 4,5,6,7,8 returns true
3. Check if tens array is sequential, return true if yes else false example 45464748 -> 45,46,47,48 returns true
4. Check if hundreds array is sequential, return true if yes else false
5. Check if thousands array is sequential, return true if yes else false
6. If it is C, the integer(for 32 bit machine) is 32 bit and it ranges from -32768 to +32767. In Java, the integer is also 32 bits but range is from -2,147,483,648 to 2,147,483,647, based on that continue checking if it is sequence of units, tens, thousands, ten thousands. Stop based on the size of the integer supported by hardware and language.
7. Once string is divided into integer then go through the integer array to determine if difference between sequential number is greater than 1 then return value +1 as missing number.