Dada una array arr[] de tamaño N y un entero X . La tarea es encontrar el elemento más pequeño mayor que X que no está presente en la array.
Ejemplos:
Entrada: arr[] = {1, 5, 10, 4, 7}, X = 4
Salida: 6
6 es el número más pequeño mayor que 4
que no está presente en la array.
Entrada: arr[] = {1, 5, 10, 6, 11}, X = 10
Salida: 12
Enfoque: Una solución eficiente se basa en la búsqueda binaria . Primero ordena la array. Tome bajo como cero y alto como N – 1 . Y busque el elemento X + 1. Si el elemento en el medio (que es (bajo + alto)/ 2) es menor o igual al elemento de búsqueda, haga bajo como medio + 1 . De lo contrario, haga alto como medio – 1 . Si el elemento en el medio es igual al elemento de búsqueda, entonces incremente el elemento de búsqueda en uno y hágalo alto como N – 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the smallest element greater
// than x which is not present in a[]
int Next_greater(int a[], int n, int x)
{
// Sort the array
sort(a, a + n);
int low = 0, high = n - 1, ans = x + 1;
// Continue until low is less
// than or equals to high
while (low <= high) {
// Find mid
int mid = (low + high) / 2;
// If element at mid is less than
// or equals to searching element
if (a[mid] <= ans) {
// If mid is equals
// to searching element
if (a[mid] == ans) {
// Increment searching element
ans++;
// Make high as N - 1
high = n - 1;
}
// Make low as mid + 1
low = mid + 1;
}
// Make high as mid - 1
else
high = mid - 1;
}
// Return the next greater element
return ans;
}
// Driver code
int main()
{
int a[] = { 1, 5, 10, 4, 7 }, x = 4;
int n = sizeof(a) / sizeof(a[0]);
cout << Next_greater(a, n, x);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the smallest element greater
// than x which is not present in a[]
static int Next_greater(int a[], int n, int x)
{
// Sort the array
Arrays.sort(a);
int low = 0, high = n - 1, ans = x + 1;
// Continue until low is less
// than or equals to high
while (low <= high)
{
// Find mid
int mid = (low + high) / 2;
// If element at mid is less than
// or equals to searching element
if (a[mid] <= ans)
{
// If mid is equals
// to searching element
if (a[mid] == ans)
{
// Increment searching element
ans++;
// Make high as N - 1
high = n - 1;
}
// Make low as mid + 1
low = mid + 1;
}
// Make high as mid - 1
else
high = mid - 1;
}
// Return the next greater element
return ans;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 5, 10, 4, 7 }, x = 4;
int n = a.length;
System.out.println(Next_greater(a, n, x));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach # Function to return the smallest element # greater than x which is not present in a[] def Next_greater(a, n, x): # Sort the array a = sorted(a) low, high, ans = 0, n - 1, x + 1 # Continue until low is less # than or equals to high while (low <= high): # Find mid mid = (low + high) // 2 # If element at mid is less than # or equals to searching element if (a[mid] <= ans): # If mid is equals # to searching element if (a[mid] == ans): # Increment searching element ans += 1 # Make high as N - 1 high = n - 1 # Make low as mid + 1 low = mid + 1 # Make high as mid - 1 else: high = mid - 1 # Return the next greater element return ans # Driver code a = [1, 5, 10, 4, 7] x = 4 n = len(a) print(Next_greater(a, n, x)) # This code is contributed # by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the smallest element greater
// than x which is not present in a[]
static int Next_greater(int []a, int n, int x)
{
// Sort the array
Array.Sort(a);
int low = 0, high = n - 1, ans = x + 1;
// Continue until low is less
// than or equals to high
while (low <= high)
{
// Find mid
int mid = (low + high) / 2;
// If element at mid is less than
// or equals to searching element
if (a[mid] <= ans)
{
// If mid is equals
// to searching element
if (a[mid] == ans)
{
// Increment searching element
ans++;
// Make high as N - 1
high = n - 1;
}
// Make low as mid + 1
low = mid + 1;
}
// Make high as mid - 1
else
high = mid - 1;
}
// Return the next greater element
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 1, 5, 10, 4, 7 };
int x = 4;
int n = a.Length;
Console.WriteLine(Next_greater(a, n, x));
}
}
// This code is contributed by Princi Singh
PHP
<?php
// PHP implementation of the approach
// Function to return the smallest element greater
// than x which is not present in a[]
function Next_greater($a, $n, $x)
{
// Sort the array
sort($a);
$low = 0;
$high = $n - 1;
$ans = $x + 1;
// Continue until low is less
// than or equals to high
while ($low <= $high)
{
// Find mid
$mid = ($low + $high) / 2;
// If element at mid is less than
// or equals to searching element
if ($a[$mid] <= $ans)
{
// If mid is equals
// to searching element
if ($a[$mid] == $ans)
{
// Increment searching element
$ans++;
// Make high as N - 1
$high = $n - 1;
}
// Make low as mid + 1
$low = $mid + 1;
}
// Make high as mid - 1
else
$high = $mid - 1;
}
// Return the next greater element
return $ans;
}
// Driver code
$a = array( 1, 5, 10, 4, 7 );
$x = 4;
$n = count($a);
echo Next_greater($a, $n, $x);
// This code is contributed by Naman_garg.
?>
Javascript
<script>
// Js implementation of the approach
// Function to return the smallest element greater
// than x which is not present in a[]
function Next_greater( a, n, x){
// Sort the array
a.sort(function(aa, bb){return aa - bb});
let low = 0, high = n - 1, ans = x + 1;
// Continue until low is less
// than or equals to high
while (low <= high) {
// Find mid
let mid = Math.floor((low + high) / 2);
// If element at mid is less than
// or equals to searching element
if (a[mid] <= ans) {
// If mid is equals
// to searching element
if (a[mid] == ans) {
// Increment searching element
ans++;
// Make high as N - 1
high = n - 1;
}
// Make low as mid + 1
low = mid + 1;
}
// Make high as mid - 1
else
high = mid - 1;
}
// Return the next greater element
return ans;
}
// Driver code
let a = [ 1, 5, 10, 4, 7 ]
let x = 4;
let n = a.length;
document.write( Next_greater(a, n, x));
</script>
Producción:
6
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA