Минимальное число больше максимального массива, которое не может быть сформировано с использованием чисел в массиве

Опубликовано: 13 Января, 2022

Учитывая массив целых чисел arr [] , задача состоит в том, чтобы найти минимальное число, превышающее максимальный элемент из массива, который не может быть сформирован с использованием чисел в массиве (добавление элементов для образования некоторого другого числа). Если такого элемента нет, выведите -1 .

Примеры:

Input: arr[] = {2, 6, 9} 
Output: -1 
There is no such number greater than 9 
that cannot be formed using 2, 6 and 9.

Input: arr[] = {6, 7, 15} 
Output: 16 
16 is the smallest number greater than 15 that 
cannot be formed using 6, 7 and 15. 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: проблема аналогична проблеме минимальной размены монеты с небольшими изменениями. Сначала отсортируйте массив в порядке возрастания и найдите максимальный элемент max, который будет числом, присутствующим в последнем индексе массива. Для ответа проверьте числа в диапазоне (макс., 2 * макс.). Если число в этом диапазоне не может быть сформировано с использованием элементов массива, тогда это число является ответом, но если все числа могут быть сформированы в этом диапазоне, то не существует такого числа, которое не может быть сформировано с использованием элементов массива.

Below is the implementation of the above approach:  

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>
Output: 
16

 

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023