Рубрики

Найдите наименьшее положительное целочисленное значение, которое не может быть представлено как сумма любого подмножества данного массива

Учитывая отсортированный массив (отсортированный в неубывающем порядке) положительных чисел, найдите наименьшее положительное целочисленное значение, которое не может быть представлено как сумма элементов любого подмножества данного набора.
Ожидаемая сложность времени O (n).

Примеры:

Input:  arr[] = {1, 3, 6, 10, 11, 15};
Output: 2

Input:  arr[] = {1, 1, 1, 1};
Output: 5

Input:  arr[] = {1, 1, 3, 4};
Output: 10

Input:  arr[] = {1, 2, 5, 10, 20, 40};
Output: 4

Input:  arr[] = {1, 2, 3, 4, 5, 6};
Output: 22

Простое решение — начать со значения 1 и проверить все значения одно за другим, если они могут суммироваться со значениями в данном массиве. Это решение очень неэффективно, так как оно сводится к задаче с суммой подмножеств, которая является хорошо известной полной задачей NP .

Мы можем решить эту проблему за O (n) раз, используя простой цикл. Пусть входной массив будет arr [0..n-1]. Мы инициализируем результат как 1 (наименьший возможный результат) и пересекаем данный массив. Пусть наименьший элемент, который не может быть представлен элементами с индексами от 0 до (i-1), будет 'res', есть следующие две возможности, когда мы рассматриваем элемент с индексом i:

1) Мы решаем, что 'res' является конечным результатом : если arr [i] больше, чем 'res', то мы нашли пробел, который равен 'res', потому что элементы после arr [i] также будут больше, чем «Рез».

2) Значение 'res' увеличивается после рассмотрения arr [i] : значение 'res' увеличивается на arr [i] (почему? Если элементы от 0 до (i-1) могут представлять от 1 до 'res- 1 ', то элементы от 0 до i могут представлять от 1 до' res + arr [i] — 1 ', добавляя' arr [i] 'ко всем подмножествам, которые представляют от 1 до' res ')

Ниже приводится реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска наименьшего положительного значения, которое не может быть
// представляется как сумма подмножеств данного отсортированного массива
#include <iostream>

using namespace std;

  
// Возвращает наименьшее число, которое не может быть представлено как сумма
// подмножества элементов из множества, представленного отсортированным массивом arr [0..n-1]

int findSmallest(int arr[], int n)

{

   int res = 1; // Инициализировать результат

  

   // Обходим массив и увеличиваем res, если arr [i]

   // меньше или равно 'res'.

   for (int i = 0; i < n && arr[i] <= res; i++)

       res = res + arr[i];

  

   return res;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

   int arr1[] = {1, 3, 4, 5};

   int n1 = sizeof(arr1)/sizeof(arr1[0]);

   cout << findSmallest(arr1, n1) << endl;

  

   int arr2[] = {1, 2, 6, 10, 11, 15};

   int n2 = sizeof(arr2)/sizeof(arr2[0]);

   cout << findSmallest(arr2, n2) << endl;

  

   int arr3[] = {1, 1, 1, 1};

   int n3 = sizeof(arr3)/sizeof(arr3[0]);

   cout << findSmallest(arr3, n3) << endl;

  

   int arr4[] = {1, 1, 3, 4};

   int n4 = sizeof(arr4)/sizeof(arr4[0]);

   cout << findSmallest(arr4, n4) << endl;

  

   return 0;

}

Джава

// Java-программа для поиска наименьшего положительного значения, которое не может быть
// представляется как сумма подмножеств данного отсортированного массива

class FindSmallestInteger 

{

    // Возвращает наименьшее число, которое не может быть представлено как сумма

    // подмножества элементов из множества, представленного отсортированным массивом arr [0..n-1]

    int findSmallest(int arr[], int n) 

    {

        int res = 1; // Инициализировать результат

  

        // Обходим массив и увеличиваем res, если arr [i]

        // меньше или равно 'res'.

        for (int i = 0; i < n && arr[i] <= res; i++)

            res = res + arr[i];

  

        return res;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        FindSmallestInteger small = new FindSmallestInteger();

        int arr1[] = {1, 3, 4, 5};

        int n1 = arr1.length;

        System.out.println(small.findSmallest(arr1, n1));

  

        int arr2[] = {1, 2, 6, 10, 11, 15};

        int n2 = arr2.length;

        System.out.println(small.findSmallest(arr2, n2));

  

        int arr3[] = {1, 1, 1, 1};

        int n3 = arr3.length;

        System.out.println(small.findSmallest(arr3, n3));

  

        int arr4[] = {1, 1, 3, 4};

        int n4 = arr4.length;

        System.out.println(small.findSmallest(arr4, n4));

  

    }

}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

python3

# Python3 программа для поиска самых маленьких
# положительное значение, которое не может быть
# представлен как сумма подмножеств
# данного отсортированного массива

  
# Возвращает наименьшее число
# которое не может быть представлено как сумма
# подмножества элементов из множества
# представлен отсортированным массивом arr [0..n-1]

def findSmallest(arr, n):

  

    res = 1 # Инициализировать результат

  

    # Обойти массив и приращение

    # 'res', если arr [i] меньше чем

    # или равно 'res'.

    for i in range (0, n ):

        if arr[i] <= res:

            res = res + arr[i]

        else:

            break

    return res

  

  
# Программа драйвера для проверки вышеуказанной функции

arr1 = [1, 3, 4, 5]

n1 = len(arr1)

print(findSmallest(arr1, n1))

  

arr2= [1, 2, 6, 10, 11, 15]

n2 = len(arr2)

print(findSmallest(arr2, n2))

  

arr3= [1, 1, 1, 1]

n3 = len(arr3)

print(findSmallest(arr3, n3))

  

arr4 = [1, 1, 3, 4]

n4 = len(arr4)

print(findSmallest(arr4, n4))

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для поиска самых маленьких
// положительное значение, которое не может быть
// представляется как сумма подмножеств
// данного отсортированного массива

using System;

  

class GFG {

      

    // Возвращает наименьшее число, которое

    // нельзя представить как сумму

    // подмножества элементов из множества

    // представлен отсортированным массивом

    // arr [0..n-1]

    static int findSmallest(int []arr, int n) 

    {

         // Инициализировать результат

         int res = 1;

  

        // Обходим массив и

        // увеличиваем res, если arr [i]

        // меньше или равно 'res'.

        for (int i = 0; i < n && 

             arr[i] <= res; i++)

            res = res + arr[i];

  

        return res;

    }

  

    // Код драйвера

    public static void Main() 

    {

        int []arr1 = {1, 3, 4, 5};

        int n1 = arr1.Length;

        Console.WriteLine(findSmallest(arr1, n1));

  

        int []arr2 = {1, 2, 6, 10, 11, 15};

        int n2 = arr2.Length;

        Console.WriteLine(findSmallest(arr2, n2));

  

        int []arr3 = {1, 1, 1, 1};

        int n3 = arr3.Length;

        Console.WriteLine(findSmallest(arr3, n3));

  

        int []arr4 = {1, 1, 3, 4};

        int n4 = arr4.Length;

        Console.WriteLine(findSmallest(arr4, n4));

  

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска самых маленьких
// положительное значение, которое не может быть
// представляется как сумма подмножеств
// данного отсортированного массива

  
// Возвращает наименьшее число, которое
// не может быть представлена как сумма
// подмножество элементов из множества
// представлен отсортированным массивом
// arr [0..n-1]

function findSmallest($arr, $n)

{

      

    // Инициализировать результат

    $res = 1; 

      

    // Обходим массив и

    // увеличиваем res, если arr [i]

    // меньше или равно 'res'.

    for($i = 0; $i < $n and $arr[$i] <= $res; $i++)

        $res = $res + $arr[$i];

      

    return $res;

}

  
// Код драйвера

$arr1 = array(1, 3, 4, 5);

$n1 = count($arr1);

echo findSmallest($arr1, $n1),"\n";

  

$arr2 = array(1, 2, 6, 10, 11, 15);

$n2 = count($arr2);

echo findSmallest($arr2, $n2),"\n" ;

  

$arr3 = array(1, 1, 1, 1);

$n3 = count($arr3);

echo findSmallest($arr3, $n3),"\n";

  

$arr4 = array(1, 1, 3, 4);

$n4 = count($arr4);

echo findSmallest($arr4, $n4);

  
// Этот код предоставлен anuj_67.
?>


Выход:

2
4
5
10

Сложность времени вышеуказанной программы O (n).

Эта статья предоставлена Рахул Гупта . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найдите наименьшее положительное целочисленное значение, которое не может быть представлено как сумма любого подмножества данного массива

0.00 (0%) 0 votes