Dada una secuencia creciente a[] , necesitamos encontrar el K-ésimo elemento contiguo faltante en la secuencia creciente que no está presente en la secuencia. Si no hay k-ésimo elemento faltante, salida -1.
Ejemplos:
Input : a[] = {2, 3, 5, 9, 10};
k = 1;
Output : 1
Explanation: Missing Element in the increasing
sequence are {1,4, 6, 7, 8}. So k-th missing element
is 1
Input : a[] = {2, 3, 5, 9, 10, 11, 12};
k = 4;
Output : 7
Explanation: missing element in the increasing
sequence are {1, 4, 6, 7, 8} so k-th missing
element is 7
Enfoque 1: Comience a iterar sobre los elementos de la array, y para cada elemento verifique si el siguiente elemento es consecutivo o no, si no, luego tome la diferencia entre estos dos y verifique si la diferencia es mayor o igual a k dada, luego calcular ans = a[i] + contar, de lo contrario iterar para el siguiente elemento.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find k-th
// missing element
int missingK(int a[], int k,
int n)
{
int difference = 0,
ans = 0, count = k;
bool flag = 0;
//case when first number is not 1
if (a[0] != 1){
difference = a[0]-1;
if (difference >= count)
return count;
count -= difference;
}
// iterating over the array
for(int i = 0 ; i < n - 1; i++)
{
difference = 0;
// check if i-th and
// (i + 1)-th element
// are not consecutive
if ((a[i] + 1) != a[i + 1])
{
// save their difference
difference +=
(a[i + 1] - a[i]) - 1;
// check for difference
// and given k
if (difference >= count)
{
ans = a[i] + count;
flag = 1;
break;
}
else
count -= difference;
}
}
// if found
if(flag)
return ans;
else
return -1;
}
// Driver code
int main()
{
// Input array
int a[] = {1, 5, 11, 19};
// k-th missing element
// to be found in the array
int k = 11;
int n = sizeof(a) / sizeof(a[0]);
// calling function to
// find missing element
int missing = missingK(a, k, n);
cout << missing << endl;
return 0;
}
Java
// Java program to check for
// even or odd
import java.io.*;
import java.util.*;
public class GFG {
// Function to find k-th
// missing element
static int missingK(int []a, int k,
int n)
{
int difference = 0,
ans = 0, count = k;
boolean flag = false;
//case when first number is not 1
if (a[0] != 1){
difference = a[0]-1;
if (difference >= count)
return count;
count -= difference;
}
// iterating over the array
for(int i = 0 ; i < n - 1; i++)
{
difference = 0;
// check if i-th and
// (i + 1)-th element
// are not consecutive
if ((a[i] + 1) != a[i + 1])
{
// save their difference
difference +=
(a[i + 1] - a[i]) - 1;
// check for difference
// and given k
if (difference >= count)
{
ans = a[i] + count;
flag = true;
break;
}
else
count -= difference;
}
}
// if found
if(flag)
return ans;
else
return -1;
}
// Driver code
public static void main(String args[])
{
// Input array
int []a = {1, 5, 11, 19};
// k-th missing element
// to be found in the array
int k = 11;
int n = a.length;
// calling function to
// find missing element
int missing = missingK(a, k, n);
System.out.print(missing);
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
Python3
# Function to find k-th # missing element def missingK(a, k, n) : difference = 0 ans = 0 count = k flag = 0 #case when first number is not 1 if a[0] != 1: difference = a[0]-1 if difference >= count: return count count -= difference # iterating over the array for i in range (0, n-1) : difference = 0 # check if i-th and # (i + 1)-th element # are not consecutive if ((a[i] + 1) != a[i + 1]) : # save their difference difference += (a[i + 1] - a[i]) - 1 # check for difference # and given k if (difference >= count) : ans = a[i] + count flag = 1 break else : count -= difference # if found if(flag) : return ans else : return -1 # Driver code # Input array a = [1, 5, 11, 19] # k-th missing element # to be found in the array k = 11 n = len(a) # calling function to # find missing element missing = missingK(a, k, n) print(missing) # This code is contributed by # Manish Shaw (manishshaw1)
C#
// C# program to check for
// even or odd
using System;
using System.Collections.Generic;
class GFG {
// Function to find k-th
// missing element
static int missingK(int []a, int k,
int n)
{
int difference = 0,
ans = 0, count = k;
bool flag = false;
//case when first number is not 1
if (a[0] != 1){
difference = a[0]-1;
if (difference >= count)
return count;
count -= difference;
}
// iterating over the array
for(int i = 0 ; i < n - 1; i++)
{
difference = 0;
// check if i-th and
// (i + 1)-th element
// are not consecutive
if ((a[i] + 1) != a[i + 1])
{
// save their difference
difference +=
(a[i + 1] - a[i]) - 1;
// check for difference
// and given k
if (difference >= count)
{
ans = a[i] + count;
flag = true;
break;
}
else
count -= difference;
}
}
// if found
if(flag)
return ans;
else
return -1;
}
// Driver code
public static void Main()
{
// Input array
int []a = {1, 5, 11, 19};
// k-th missing element
// to be found in the array
int k = 11;
int n = a.Length;
// calling function to
// find missing element
int missing = missingK(a, k, n);
Console.Write(missing);
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
PHP
<?php
// Function to find k-th
// missing element
function missingK(&$a, $k, $n)
{
$difference = 0;
$ans = 0;
$count = $k;
$flag = 0;
// iterating over the array
for($i = 0 ; $i < $n - 1; $i++)
{
$difference = 0;
// check if i-th and
// (i + 1)-th element
// are not consecutive
if (($a[$i] + 1) != $a[$i + 1])
{
// save their difference
$difference += ($a[$i + 1] -
$a[$i]) - 1;
// check for difference
// and given k
if ($difference >= $count)
{
$ans = $a[$i] + $count;
$flag = 1;
break;
}
else
$count -= $difference;
}
}
// if found
if($flag)
return $ans;
else
return -1;
}
// Driver Code
// Input array
$a = array(1, 5, 11, 19);
// k-th missing element
// to be found in the array
$k = 11;
$n = count($a);
// calling function to
// find missing element
$missing = missingK($a, $k, $n);
echo $missing;
// This code is contributed by Manish Shaw
// (manishshaw1)
?>
Javascript
<script>
// Javascript program to check for
// even or odd
// Function to find k-th
// missing element
function missingK(a, k, n)
{
let difference = 0, ans = 0, count = k;
let flag = false;
//case when first number is not 1
if (a[0] != 1){
difference = a[0]-1;
if (difference >= count){
return count;
}
count -= difference;
}
// iterating over the array
for(let i = 0 ; i < n - 1; i++)
{
difference = 0;
// Check if i-th and
// (i + 1)-th element
// are not consecutive
if ((a[i] + 1) != a[i + 1])
{
// Save their difference
difference += (a[i + 1] - a[i]) - 1;
// Check for difference
// and given k
if (difference >= count)
{
ans = a[i] + count;
flag = true;
break;
}
else
count -= difference;
}
}
// If found
if (flag)
return ans;
else
return -1;
}
// Driver code
// Input array
let a = [ 1, 5, 11, 19 ];
// k-th missing element
// to be found in the array
let k = 11;
let n = a.length;
// Calling function to
// find missing element
let missing = missingK(a, k, n);
document.write(missing);
// This code is contributed by suresh07
</script>
Producción
14
Complejidad de tiempo: O(n), donde n es el número de elementos en la array.
Enfoque 2:
Aplicar una búsqueda binaria. Dado que la array está ordenada, podemos encontrar en cualquier índice dado cuántos números faltan como arr[índice] – (índice+1). Aprovecharíamos este conocimiento y aplicaríamos la búsqueda binaria para reducir nuestra búsqueda y encontrar ese índice desde el cual obtener el número que falta es más fácil.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for above approach
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Function to find
// kth missing number
int missingK(vector<int>& arr, int k)
{
int n = arr.size();
int l = 0, u = n - 1, mid;
while(l <= u)
{
mid = (l + u)/2;
int numbers_less_than_mid = arr[mid] -
(mid + 1);
// If the total missing number
// count is equal to k we can iterate
// backwards for the first missing number
// and that will be the answer.
if(numbers_less_than_mid == k)
{
// To further optimize we check
// if the previous element's
// missing number count is equal
// to k. Eg: arr = [4,5,6,7,8]
// If you observe in the example array,
// the total count of missing numbers for all
// the indices are same, and we are
// aiming to narrow down the
// search window and achieve O(logn)
// time complexity which
// otherwise would've been O(n).
if(mid > 0 && (arr[mid - 1] - (mid)) == k)
{
u = mid - 1;
continue;
}
// Else we return arr[mid] - 1.
return arr[mid]-1;
}
// Here we appropriately
// narrow down the search window.
if(numbers_less_than_mid < k)
{
l = mid + 1;
}
else if(k < numbers_less_than_mid)
{
u = mid - 1;
}
}
// In case the upper limit is -ve
// it means the missing number set
// is 1,2,..,k and hence we directly return k.
if(u < 0)
return k;
// Else we find the residual count
// of numbers which we'd then add to
// arr[u] and get the missing kth number.
int less = arr[u] - (u + 1);
k -= less;
// Return arr[u] + k
return arr[u] + k;
}
// Driver Code
int main()
{
vector<int> arr = {2,3,4,7,11};
int k = 5;
// Function Call
cout <<"Missing kth number = "<<
missingK(arr, k)<<endl;
return 0;
}
Java
// Java program for above approach
public class GFG
{
// Function to find
// kth missing number
static int missingK(int[] arr, int k)
{
int n = arr.length;
int l = 0, u = n - 1, mid;
while(l <= u)
{
mid = (l + u)/2;
int numbers_less_than_mid = arr[mid] -
(mid + 1);
// If the total missing number
// count is equal to k we can iterate
// backwards for the first missing number
// and that will be the answer.
if(numbers_less_than_mid == k)
{
// To further optimize we check
// if the previous element's
// missing number count is equal
// to k. Eg: arr = [4,5,6,7,8]
// If you observe in the example array,
// the total count of missing numbers for all
// the indices are same, and we are
// aiming to narrow down the
// search window and achieve O(logn)
// time complexity which
// otherwise would've been O(n).
if(mid > 0 && (arr[mid - 1] - (mid)) == k)
{
u = mid - 1;
continue;
}
// Else we return arr[mid] - 1.
return arr[mid] - 1;
}
// Here we appropriately
// narrow down the search window.
if(numbers_less_than_mid < k)
{
l = mid + 1;
}
else if(k < numbers_less_than_mid)
{
u = mid - 1;
}
}
// In case the upper limit is -ve
// it means the missing number set
// is 1,2,..,k and hence we directly return k.
if(u < 0)
return k;
// Else we find the residual count
// of numbers which we'd then add to
// arr[u] and get the missing kth number.
int less = arr[u] - (u + 1);
k -= less;
// Return arr[u] + k
return arr[u] + k;
}
// Driver code
public static void main(String[] args)
{
int[] arr = {2,3,4,7,11};
int k = 5;
// Function Call
System.out.println("Missing kth number = "+ missingK(arr, k));
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program for above approach
# Function to find
# kth missing number
def missingK(arr, k):
n = len(arr)
l = 0
u = n - 1
mid = 0
while(l <= u):
mid = (l + u)//2;
numbers_less_than_mid = arr[mid] - (mid + 1);
# If the total missing number
# count is equal to k we can iterate
# backwards for the first missing number
# and that will be the answer.
if(numbers_less_than_mid == k):
# To further optimize we check
# if the previous element's
# missing number count is equal
# to k. Eg: arr = [4,5,6,7,8]
# If you observe in the example array,
# the total count of missing numbers for all
# the indices are same, and we are
# aiming to narrow down the
# search window and achieve O(logn)
# time complexity which
# otherwise would've been O(n).
if(mid > 0 and (arr[mid - 1] - (mid)) == k):
u = mid - 1;
continue;
# Else we return arr[mid] - 1.
return arr[mid]-1;
# Here we appropriately
# narrow down the search window.
if(numbers_less_than_mid < k):
l = mid + 1;
elif(k < numbers_less_than_mid):
u = mid - 1;
# In case the upper limit is -ve
# it means the missing number set
# is 1,2,..,k and hence we directly return k.
if(u < 0):
return k;
# Else we find the residual count
# of numbers which we'd then add to
# arr[u] and get the missing kth number.
less = arr[u] - (u + 1);
k -= less;
# Return arr[u] + k
return arr[u] + k;
# Driver Code
if __name__=='__main__':
arr = [2,3,4,7,11];
k = 5;
# Function Call
print("Missing kth number = "+ str(missingK(arr, k)))
# This code is contributed by rutvik_56.
C#
// C# program for above approach
using System;
class GFG {
// Function to find
// kth missing number
static int missingK(int[] arr, int k)
{
int n = arr.Length;
int l = 0, u = n - 1, mid;
while(l <= u)
{
mid = (l + u)/2;
int numbers_less_than_mid = arr[mid] -
(mid + 1);
// If the total missing number
// count is equal to k we can iterate
// backwards for the first missing number
// and that will be the answer.
if(numbers_less_than_mid == k)
{
// To further optimize we check
// if the previous element's
// missing number count is equal
// to k. Eg: arr = [4,5,6,7,8]
// If you observe in the example array,
// the total count of missing numbers for all
// the indices are same, and we are
// aiming to narrow down the
// search window and achieve O(logn)
// time complexity which
// otherwise would've been O(n).
if(mid > 0 && (arr[mid - 1] - (mid)) == k)
{
u = mid - 1;
continue;
}
// Else we return arr[mid] - 1.
return arr[mid] - 1;
}
// Here we appropriately
// narrow down the search window.
if(numbers_less_than_mid < k)
{
l = mid + 1;
}
else if(k < numbers_less_than_mid)
{
u = mid - 1;
}
}
// In case the upper limit is -ve
// it means the missing number set
// is 1,2,..,k and hence we directly return k.
if(u < 0)
return k;
// Else we find the residual count
// of numbers which we'd then add to
// arr[u] and get the missing kth number.
int less = arr[u] - (u + 1);
k -= less;
// Return arr[u] + k
return arr[u] + k;
}
// Driver code
static void Main()
{
int[] arr = {2,3,4,7,11};
int k = 5;
// Function Call
Console.WriteLine("Missing kth number = "+ missingK(arr, k));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript program for above approach
// Function to find
// kth missing number
function missingK(arr, k)
{
var n = arr.length;
var l = 0, u = n - 1, mid;
while(l <= u)
{
mid = (l + u)/2;
var numbers_less_than_mid = arr[mid] -
(mid + 1);
// If the total missing number
// count is equal to k we can iterate
// backwards for the first missing number
// and that will be the answer.
if(numbers_less_than_mid == k)
{
// To further optimize we check
// if the previous element's
// missing number count is equal
// to k. Eg: arr = [4,5,6,7,8]
// If you observe in the example array,
// the total count of missing numbers for all
// the indices are same, and we are
// aiming to narrow down the
// search window and achieve O(logn)
// time complexity which
// otherwise would've been O(n).
if(mid > 0 && (arr[mid - 1] - (mid)) == k)
{
u = mid - 1;
continue;
}
// Else we return arr[mid] - 1.
return arr[mid] - 1;
}
// Here we appropriately
// narrow down the search window.
if(numbers_less_than_mid < k)
{
l = mid + 1;
}
else if(k < numbers_less_than_mid)
{
u = mid - 1;
}
}
// In case the upper limit is -ve
// it means the missing number set
// is 1,2,..,k and hence we directly return k.
if(u < 0)
return k;
// Else we find the residual count
// of numbers which we'd then add to
// arr[u] and get the missing kth number.
var less = arr[u] - (u + 1);
k -= less;
// Return arr[u] + k
return arr[u] + k;
}
// Driver code
var arr = [2,3,4,7,11];
var k = 5;
// Function Call
document.write("Missing kth number = "+ missingK(arr, k));
// This code is contributed by shivanisinghss2110
</script>
Producción
Missing kth number = 9
Complejidad de tiempo: O (logn), donde n es el número de elementos en la array.
Enfoque 3 (usando el mapa): atravesaremos la array y marcaremos cada uno de los elementos como visitados en el mapa y también realizaremos un seguimiento del elemento mínimo y máximo presente para que sepamos el límite inferior y superior para la entrada particular dada . Luego comenzamos un ciclo desde el límite inferior al superior y mantenemos una variable de conteo. Tan pronto como encontramos un elemento que no está presente en el mapa, incrementamos la cuenta y hasta que la cuenta sea igual a k.
C++14
#include <iostream>
#include <unordered_map>
using namespace std;
int solve(int arr[] , int k , int n)
{
unordered_map<int ,int> umap;
int mins = 99999;
int maxs = -99999;
for(int i=0 ; i<n ; i++)
{
umap[arr[i]] = 1; //mark each element of array in map
if(mins > arr[i])
mins = arr[i]; //keeping track of minimum element
if(maxs < arr[i])
maxs = arr[i]; //keeping track of maximum element i.e. upper bound
}
int counts = 0;
//iterate from lower to upper bound
for(int i=mins ; i<=maxs ; i++)
{
if(umap[i] == 0)
counts++;
if(counts == k)
return i;
}
return -1;
}
int main() {
int arr[] = {2, 3, 5, 9, 10, 11, 12} ;
int k = 4;
cout << solve(arr , k , 7) ; //(array , k , size of array)
return 0;
}
Java
// Java approach
// Importing HashMap class
import java.util.HashMap;
class GFG {
public static int solve(int arr[] , int k , int n)
{
HashMap<Integer, Integer> umap = new HashMap<Integer, Integer>();
int mins = 99999;
int maxs = -99999;
for(int i = 0; i < n; i++)
{
umap.put(arr[i], 1); // mark each element of array in map
if(mins > arr[i])
mins = arr[i]; // keeping track of minimum element
if(maxs < arr[i])
maxs = arr[i]; // keeping track of maximum element i.e. upper bound
}
int counts = 0;
// iterate from lower to upper bound
for(int i = mins; i <= maxs; i++)
{
if(umap.get(i) == null)
counts++;
if(counts == k)
return i;
}
return -1;
}
public static void main (String[] args)
{
int arr[] = {2, 3, 5, 9, 10, 11, 12} ;
int k = 4;
System.out.println(solve(arr , k , 7)); //(array , k , size of array)
}
}
// This code is contributed by Shubham Singh
Python3
# Python approach
def solve( arr , k , n):
umap = {}
mins = 99999
maxs = -99999
for i in range(n):
umap[arr[i]] = 1 #mark each element of array in map
if(mins > arr[i]):
mins = arr[i] #keeping track of minimum element
if(maxs < arr[i]):
maxs = arr[i] #keeping track of maximum element i.e. upper bound
counts = 0
# iterate from lower to upper bound
for i in range(mins, maxs+1):
if(i not in umap):
counts += 1
if(counts == k):
return i
return -1
arr = [2, 3, 5, 9, 10, 11, 12]
k = 4
print(solve(arr , k , 7)) #(array , k , size of array)
# This code is contributed
# by Shubham Singh
C#
// C# program for above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find
// kth missing number
static int solve(int[] arr, int k, int n)
{
Dictionary < int, int > umap = new Dictionary < int, int > ();
int mins = 99999;
int maxs = -99999;
for(int i=0 ; i<n ; i++)
{
umap.Add(arr[i], 1); //mark each element of array in map
if(mins > arr[i])
mins = arr[i]; //keeping track of minimum element
if(maxs < arr[i])
maxs = arr[i]; //keeping track of maximum element i.e. upper bound
}
int counts = 0;
//iterate from lower to upper bound
for(int i=mins ; i<=maxs ; i++)
{
if(!umap.ContainsKey(i))
counts++;
if(counts == k)
return i;
}
return -1;
}
// Driver code
static void Main()
{
int[] arr = {2, 3, 5, 9, 10, 11, 12};
int k = 4;
int n = arr.Length;
// Function Call
Console.WriteLine("Missing kth number = "+ solve(arr , k , n)) ;
//(array , k , size of array));
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// JavaScript program
function solve(arr ,k ,n){
let umap = new Map()
let mins = 99999
let maxs = -99999
for(let i = 0; i < n; i++){
umap.set(arr[i] , 1) //mark each element of array in map
if(mins > arr[i])
mins = arr[i] //keeping track of minimum element
if(maxs < arr[i])
maxs = arr[i] //keeping track of maximum element i.e. upper bound
}
let counts = 0
// iterate from lower to upper bound
for(let i = mins; i < maxs + 1; i++){
if(!umap.has(i))
counts += 1
if(counts == k)
return i
}
return -1
}
// driver code
let arr = [2, 3, 5, 9, 10, 11, 12]
let k = 4
document.write(solve(arr , k , 7),"</br>") //(array , k , size of array)
// This code is contributed by shinjanpatra
</script>
Producción
8
Complejidad temporal: O(n+m), donde n es el número de elementos del arreglo y m es la diferencia entre los
el elemento más grande y más pequeño de la array.