Количество различных целых чисел в диапазоне [1, N], которые не имеют суммы подмножеств в виде K
Опубликовано: 22 Сентября, 2022
Даны два положительных целых числа N и K , такие что K≤N, задача состоит в том, чтобы найти максимальное количество различных целых чисел в диапазоне [1, N] , не имеющих подмножества с суммой, равной K . Если решений несколько, выведите любое.
Примеры:
Input: N = 5, K = 3
Output: 1 4 5
Explanation: There are two sets of distinct numbers of size 3 which don’t have any subset sum of 3.
These are {1, 4, 5} and {2, 4, 5}. So, print any of them in any order.Input: N = 1, K =1
Output: 0
Подход: Идея основана на следующих наблюдениях:
- Можно выбрать любое число больше K , поскольку они никогда не могут вносить вклад в подмножество, сумма которого равна K.
- К нельзя выбрать.
- Для чисел меньше K можно выбрать не более K/2 чисел. Например:
- Если K = 5, 1 + 4 = 5 и 2 + 3 = 5, то можно выбрать либо 1, либо 4, и аналогичным образом можно выбрать либо 2, либо 3. Таким образом, можно выбрать не более (5/2=2) чисел.
- Если К =6, 1+5=6, 2+4=6 и 3+3=6. Опять же, можно выбрать 3 числа так, чтобы никакая сумма подмножества не равнялась 6. Всегда можно выбрать 3, поскольку выбираются только разные числа, и можно выбрать либо 1, либо 5, и аналогичным образом либо 2, либо 4. Таким образом, можно выбрать не более (6/3=3) чисел.
- Следовательно, максимальное количество различных чисел, которые можно выбрать, равно (NK)+(K/2) .
Выполните следующие шаги, чтобы решить проблему:
- Максимальное количество различных цифр, которое можно выбрать, равно (NK)+(K/2) .
- Необходимо выбрать все числа больше K , т.е. NK номеров с конца. Также необходимо выбрать K/2 элементов меньше K.
- Таким образом, возможное решение состоит в том, чтобы выбрать (NK)+(K/2) последовательных чисел, начиная с N и исключая K .
- Самый простой способ сделать это — создать массив, содержащий все значения от 1 до N , кроме K , перевернуть массив и вывести (NK)+(K/2) элементов с начала.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)