Dada una array arr[] de enteros, la tarea es encontrar el número mínimo mayor que el elemento máximo de la array que no se puede formar usando los números de la array (agregando elementos para formar algún otro número). Si no existe tal elemento, imprima -1 .
Ejemplos:
Entrada: arr[] = {2, 6, 9}
Salida: -1
No existe un número mayor que 9
que no se pueda formar usando 2, 6 y 9.Entrada: arr[] = {6, 7, 15}
Salida: 16
16 es el número más pequeño mayor que 15 que
no se puede formar usando 6, 7 y 15.
Enfoque: El problema es similar al problema de cambio mínimo de moneda con una ligera modificación. Primero ordene la array en orden ascendente y encuentre el elemento máximo máximo que será el número presente en el último índice de la array. Verifique los números en el rango (máx., 2 * máx.) para la respuesta. Si un número en este rango no se puede formar usando los elementos de la array, entonces ese número es la respuesta, pero si todos los números se pueden formar en este rango, entonces no existe tal número que no se pueda formar usando los elementos de la array.
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 that returns the minimum
// number greater than maximum of the
// array that cannot be formed using the
// elements of the array
int findNumber(int arr[], int n)
{
// Sort the given array
sort(arr, arr + n);
// Maximum number in the array
int max = arr[n - 1];
// table[i] will store the minimum number of
// elements from the array to form i
int table[(2 * max) + 1];
table[0] = 0;
for (int i = 1; i < (2 * max) + 1; i++)
table[i] = INT_MAX;
int ans = -1;
// Calculate the minimum number of elements
// from the array required to form
// the numbers from 1 to (2 * max)
for (int i = 1; i < (2 * max) + 1; i++) {
for (int j = 0; j < n; j++) {
if (arr[j] <= i) {
int res = table[i - arr[j]];
if (res != INT_MAX && res + 1 < table[i])
table[i] = res + 1;
}
}
// If there exists a number greater than
// the maximum element of the array that can be
// formed using the numbers of array
if (i > arr[n - 1] && table[i] == INT_MAX) {
ans = i;
break;
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 6, 7, 15 };
int n = (sizeof(arr) / sizeof(int));
cout << findNumber(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG
{
// Function that returns the minimum
// number greater than maximum of the
// array that cannot be formed using the
// elements of the array
static int findNumber(int arr[], int n)
{
// Sort the given array
Arrays.sort(arr);
// Maximum number in the array
int max = arr[n - 1];
// table[i] will store the minimum number of
// elements from the array to form i
int table[] = new int[(2 * max) + 1];
table[0] = 0;
for (int i = 1; i < (2 * max) + 1; i++)
table[i] = Integer.MAX_VALUE;
int ans = -1;
// Calculate the minimum number of elements
// from the array required to form
// the numbers from 1 to (2 * max)
for (int i = 1; i < (2 * max) + 1; i++)
{
for (int j = 0; j < n; j++)
{
if (arr[j] <= i)
{
int res = table[i - arr[j]];
if (res != Integer.MAX_VALUE && res + 1 < table[i])
table[i] = res + 1;
}
}
// If there exists a number greater than
// the maximum element of the array that can be
// formed using the numbers of array
if (i > arr[n - 1] && table[i] == Integer.MAX_VALUE)
{
ans = i;
break;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 7, 15 };
int n = arr.length;
System.out.println(findNumber(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach # Function that returns the minimum # number greater than Maximum of the # array that cannot be formed using the # elements of the array def findNumber(arr, n): # Sort the given array arr = sorted(arr) # Maximum number in the array Max = arr[n - 1] # table[i] will store the minimum number of # elements from the array to form i table = [10**9 for i in range((2 * Max) + 1)] table[0] = 0 ans = -1 # Calculate the minimum number of elements # from the array required to form # the numbers from 1 to (2 * Max) for i in range(1, 2 * Max + 1): for j in range(n): if (arr[j] <= i): res = table[i - arr[j]] if (res != 10**9 and res + 1 < table[i]): table[i] = res + 1 # If there exists a number greater than # the Maximum element of the array that can be # formed using the numbers of array if (i > arr[n - 1] and table[i] == 10**9): ans = i break return ans # Driver code arr = [6, 7, 15] n = len(arr) print(findNumber(arr, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns the minimum
// number greater than maximum of the
// array that cannot be formed using the
// elements of the array
static int findNumber(int[] arr, int n)
{
// Sort the given array
Array.Sort(arr);
// Maximum number in the array
int max = arr[n - 1];
// table[i] will store the minimum number of
// elements from the array to form i
int[] table = new int[(2 * max) + 1];
table[0] = 0;
for (int i = 1; i < (2 * max) + 1; i++)
table[i] = int.MaxValue;
int ans = -1;
// Calculate the minimum number of elements
// from the array required to form
// the numbers from 1 to (2 * max)
for (int i = 1; i < (2 * max) + 1; i++)
{
for (int j = 0; j < n; j++)
{
if (arr[j] <= i)
{
int res = table[i - arr[j]];
if (res != int.MaxValue && res + 1 < table[i])
table[i] = res + 1;
}
}
// If there exists a number greater than
// the maximum element of the array that can be
// formed using the numbers of array
if (i > arr[n - 1] && table[i] == int.MaxValue)
{
ans = i;
break;
}
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 6, 7, 15 };
int n = arr.Length;
Console.WriteLine(findNumber(arr, n));
}
}
/* This code contributed by Code_Mech */
PHP
<?PHP
// PHP implementation of the approach
// Function that returns the minimum
// number greater than maximum of the
// array that cannot be formed using the
// elements of the array
function findNumber($arr, $n)
{
// Sort the given array
sort($arr);
// Maximum number in the array
$max = $arr[$n - 1];
// table[i] will store the minimum number of
// elements from the array to form i
$table = array((2 * $max) + 1);
$table[0] = 0;
for ($i = 1; $i < (2 * $max) + 1; $i++)
$table[$i] = PHP_INT_MAX;
$ans = -1;
// Calculate the minimum number of elements
// from the array required to form
// the numbers from 1 to (2 * max)
for ($i = 1; $i < (2 * $max) + 1; $i++)
{
for ($j = 0; $j < $n; $j++)
{
if ($arr[$j] <= $i)
{
$res = $table[$i - $arr[$j]];
if ($res != PHP_INT_MAX && $res + 1 < $table[$i])
$table[$i] = $res + 1;
}
}
// If there exists a number greater than
// the maximum element of the array that can be
// formed using the numbers of array
if ($i > $arr[$n - 1] && $table[$i] == PHP_INT_MAX)
{
$ans = $i;
break;
}
}
return $ans;
}
// Driver code
{
$arr = array(6, 7, 15 );
$n = sizeof($arr);
echo(findNumber($arr, $n));
}
/* This code contributed by Code_Mech*/
Javascript
<script>
// Javascript implementation of the approach
// Function that returns the minimum
// number greater than maximum of the
// array that cannot be formed using the
// elements of the array
function findNumber(arr, n)
{
// Sort the given array
arr.sort((a, b) => a - b);
// Maximum number in the array
var max = arr[n - 1];
// table[i] will store the minimum number of
// elements from the array to form i
var table = Array((2 * max) + 1).fill(0);
table[0] = 0;
for(i = 1; i < (2 * max) + 1; i++)
table[i] = Number.MAX_VALUE;
var ans = -1;
// Calculate the minimum number of elements
// from the array required to form
// the numbers from 1 to (2 * max)
for(i = 1; i < (2 * max) + 1; i++)
{
for(j = 0; j < n; j++)
{
if (arr[j] <= i)
{
var res = table[i - arr[j]];
if (res != Number.MAX_VALUE &&
res + 1 < table[i])
table[i] = res + 1;
}
}
// If there exists a number greater than
// the maximum element of the array that can be
// formed using the numbers of array
if (i > arr[n - 1] &&
table[i] == Number.MAX_VALUE)
{
ans = i;
break;
}
}
return ans;
}
// Driver code
var arr = [ 6, 7, 15 ];
var n = arr.length;
document.write(findNumber(arr, n));
// This code is contributed by umadevi9616
</script>
Producción:
16
Complejidad de tiempo: O(MAX * N)
Espacio auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA