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

01.01.2020Массивы

Учитывая отсортированный массив (отсортированный в неубывающем порядке) положительных чисел, найдите наименьшее положительное целочисленное значение, которое не может быть представлено как сумма элементов любого подмножества данного набора.
Ожидаемая сложность времени 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.
?>

Выход:

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

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

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

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

0.00 (0%) 0 votes