Dada una string que consta de algunos números, no separados por ningún separador. Los números son enteros positivos y la secuencia aumenta en uno en cada número excepto en el número que falta. La tarea es encontrar el número que falta. Los números no tendrán más de seis dígitos. Imprime -1 si la secuencia de entrada no es válida.
Ejemplos:
Input : 89101113 Output : 12 Input : 9899101102 Output : 100 Input : 596597598600601602: Output : 599 Input : 909192939495969798100101 Output : 99 Input : 11111211311411511 Output : -1
La idea es probar todas las longitudes del 1 al 6. Para cada longitud que intentamos, verificamos si la longitud actual satisface la propiedad de todos los números consecutivos y falta uno. Una cosa interesante es que la cantidad de dígitos puede cambiar a medida que incrementamos los números. Por ejemplo, cuando nos movemos de 99 a 100. Para manejar esta situación, encontramos el número de dígitos usando la base logarítmica 10.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find a missing number in a
// string of consecutive numbers without any
// separator.
#include<bits/stdc++.h>
using namespace std;
const int MAX_DIGITS = 6;
// gets the integer at position i with length m,
// returns it or -1, if none
int getValue(const string& str, int i, int m)
{
if (i + m > str.length())
return -1;
// Find value at index i and length m.
int value = 0;
for (int j = 0; j < m; j++)
{
int c = str[i + j] - '0';
if (c < 0 || c > 9)
return -1;
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
int findMissingNumber(const string& str)
{
// Try all lengths for first number
for (int m=1; m<=MAX_DIGITS; ++m)
{
// Get value of first number with current
// length/
int n = getValue(str, 0, m);
if (n == -1)
break;
// To store missing number of current length
int missingNo = -1;
// To indicate whether the sequence failed
// anywhere for current length.
bool fail = false;
// Find subsequent numbers with previous number as n
for (int i=m; i!=str.length(); i += 1 + log10l(n))
{
// If we haven't yet found the missing number
// for current length. Next number is n+2. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1) &&
(getValue(str, i, 1+log10l(n+2)) == n+2))
{
missingNo = n + 1;
n += 2;
}
// If next value is (n+1)
else if (getValue(str, i, 1+log10l(n+1)) == n+1)
n++;
else
{
fail = true;
break;
}
}
if (!fail)
return missingNo;
}
return -1; // not found or no missing number
}
// Driver code
int main()
{
cout << findMissingNumber("99101102");
return 0;
}
Java
// Java program to find a missing number in a
// string of consecutive numbers without any
// separator.
class GFG {
static final int MAX_DIGITS = 6;
// gets the integer at position i with length m,
// returns it or -1, if none
static int getValue(String str, int i, int m) {
if (i + m > str.length()) {
return -1;
}
// Find value at index i and length m.
int value = 0;
for (int j = 0; j < m; j++) {
int c = str.charAt(i + j) - '0';
if (c < 0 || c > 9) {
return -1;
}
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
static int findMissingNumber(String str) {
// Try all lengths for first number
for (int m = 1; m <= MAX_DIGITS; ++m) {
// Get value of first number with current
// length/
int n = getValue(str, 0, m);
if (n == -1) {
break;
}
// To store missing number of current length
int missingNo = -1;
// To indicate whether the sequence failed
// anywhere for current length.
boolean fail = false;
// Find subsequent numbers with previous number as n
for (int i = m; i != str.length(); i += 1 + Math.log10(n)) {
// If we haven't yet found the missing number
// for current length. Next number is n+2. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1)
&& (getValue(str, i, (int) (1 + Math.log10(n + 2))) == n + 2)) {
missingNo = n + 1;
n += 2;
} // If next value is (n+1)
else if (getValue(str, i, (int) (1 + Math.log10(n + 1))) == n + 1) {
n++;
} else {
fail = true;
break;
}
}
if (!fail) {
return missingNo;
}
}
return -1; // not found or no missing number
}
// Driver code
public static void main(String[] args) {
System.out.println(findMissingNumber("99101102"));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find
# a missing number in a
# string of consecutive
# numbers without any
# separator.
import math
MAX_DIGITS = 6
# gets the integer at position
# i with length m, returns it
# or -1, if none
def getValue(Str, i, m):
if(i + m > len(Str)):
return -1
# Find value at index
# i and length m.
value = 0
for j in range(m):
c = (ord(Str[i + j]) -
ord('0'))
if(c < 0 or c > 9):
return -1
value = value * 10 + c
return value
# Returns value of missing
# number
def findMissingNumber(Str):
# Try all lengths for
#first number
for m in range(1, MAX_DIGITS + 1):
# Get value of first
# number with current
# length
n = getValue(Str, 0, m)
if(n == -1):
break
# To store missing number
# of current length
missingNo = -1
# To indicate whether
# the sequence failed
# anywhere for current
# length.
fail = False
# Find subsequent numbers
# with previous number as n
i = m
while(i != len(Str)):
# If we haven't yet found
# the missing number for
# current length. Next
# number is n+2. Note
# that we use Log10 as
# (n+2) may have more
# length than n.
if((missingNo == -1) and
(getValue(Str, i, 1 +
int(math.log10(n + 2))) ==
n + 2)):
missingNo = n + 1
n += 2
# If next value is (n+1)
elif((getValue(Str, i, 1 +
int(math.log10(n + 1))) ==
n + 1)):
n += 1
else:
fail = True
break
i += 1 + int(math.log10(n))
if(not fail):
return missingNo
# not found or no
# missing number
return -1
# Driver code
print(findMissingNumber("99101102"))
# This code is contributed by avanitrachhadiya2155
C#
// C# program to find a missing number in a
// string of consecutive numbers without any
// separator.
using System;
public class GFG {
static readonly int MAX_DIGITS = 6;
// gets the integer at position i with length m,
// returns it or -1, if none
static int getValue(String str, int i, int m) {
if (i + m > str.Length) {
return -1;
}
// Find value at index i and length m.
int value = 0;
for (int j = 0; j < m; j++) {
int c = str[i + j] - '0';
if (c < 0 || c > 9) {
return -1;
}
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
static int findMissingNumber(String str) {
// Try all lengths for first number
for (int m = 1; m <= MAX_DIGITS; ++m) {
// Get value of first number with current
// length/
int n = getValue(str, 0, m);
if (n == -1) {
break;
}
// To store missing number of current length
int missingNo = -1;
// To indicate whether the sequence failed
// anywhere for current length.
bool fail = false;
// Find subsequent numbers with previous number as n
for (int i = m; i != str.Length; i += 1 + (int)Math.Log10(n)) {
// If we haven't yet found the missing number
// for current length. Next number is n+2. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1)
&& (getValue(str, i, (int) (1 + Math.Log10(n + 2))) == n + 2)) {
missingNo = n + 1;
n += 2;
} // If next value is (n+1)
else if (getValue(str, i, (int) (1 + Math.Log10(n + 1))) == n + 1) {
n++;
} else {
fail = true;
break;
}
}
if (!fail) {
return missingNo;
}
}
return -1; // not found or no missing number
}
// Driver code
public static void Main() {
Console.WriteLine(findMissingNumber("99101102"));
}
}
//This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find a missing number
// in a string of consecutive numbers without any
// separator.
let MAX_DIGITS = 6;
// Gets the integer at position i
// with length m, returns it or -1,
// if none
function getValue(str, i, m)
{
if (i + m > str.length)
{
return -1;
}
// Find value at index i and length m.
let value = 0;
for(let j = 0; j < m; j++)
{
let c = str[i + j].charCodeAt(0) -
'0'.charCodeAt(0);
if (c < 0 || c > 9)
{
return -1;
}
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
function findMissingNumber(str)
{
// Try all lengths for first number
for(let m = 1; m <= MAX_DIGITS; ++m)
{
// Get value of first number with
// current length
let n = getValue(str, 0, m);
if (n == -1)
{
break;
}
// To store missing number of
// current length
let missingNo = -1;
// To indicate whether the sequence
// failed anywhere for current length.
let fail = false;
// Find subsequent numbers with
// previous number as n
for(let i = m;
i != str.length;
i += 1 + Math.floor(Math.log10(n)))
{
// If we haven't yet found the missing number
// for current length. Next number is n+2. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1) &&
(getValue(str, i, Math.floor(1 + Math.log10(n + 2))) == n + 2)) {
missingNo = n + 1;
n += 2;
}
// If next value is (n+1)
else if (getValue(str, i, Math.floor(
1 + Math.log10(n + 1))) == n + 1)
{
n++;
}
else
{
fail = true;
break;
}
}
if (!fail)
{
return missingNo;
}
}
// Not found or no missing number
return -1;
}
// Driver code
document.write(findMissingNumber("99101102"));
// This code is contributed by ab2127
</script>
Producción
100
Este artículo es una contribución de Roshni Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA