Минимизируйте умножение подпоследовательности, чтобы преобразовать сумму массива в степень 2

Опубликовано: 25 Февраля, 2023

Дан массив A[] размера N , каждый элемент которого является положительной степенью числа 2. За одну операцию выберите непустую подпоследовательность массива и умножьте все элементы подпоследовательности на любое положительное целое число, такое что сумма массив становится степенью двойки. Задача состоит в том, чтобы минимизировать эту операцию.

Примеры:

Input: S = {4, 8, 4, 32}   
Output: 
1
5 
{4}

Explanation: Choose a subsequence {4} and multiplying it by 5 
turns the array into [20, 8, 4, 32], whose sum is 64 = 26. 
Hence minimum number of operations required to make 
sum of sequence into power of 2 is 1.

Input: S = {2, 2, 4, 8}
Output: 0
Explanation: The array already has a sum 16 which is power of 2.

Подход: Задача может быть решена на основе следующего наблюдения:

Наблюдения:

If the sum of sequence is already power of 2, we need 0 operations.

Otherwise, we can make do itusing exactly one operation.                                                                                                        

  • Let S be the sum of the sequence. We know that S is not a power of 2. After some number of operations, let us assume  that we achieve a sum of 2r.
  • S < 2r: This is because, in each operation we multiply some subsequence with a positive integer. This would increase the value of the elements of that subsequence and thus the overall sum.
  • This means that we have to increase S at least to 2r such that 2r−1 < S < 2r. For this, we need to add 2r − S to the sequence.
    Let M denote the smallest element of the sequence. Then 2r − S is a multiple of M.

To convert S to 2r, we can simply multiply M by (2r − (S − M)) / M. This would take only one operation and make the sum of sequence equal to a power of 2. The chosen subsequence in the operation only consists of M.

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

  • Проверьте, является ли последовательность уже степенью 2, тогда ответ равен 0.
  • В противном случае нам потребуется только 1 операция
    • Пусть S будет суммой последовательности (где S не является степенью числа 2), а r будет наименьшим целым числом таким, что S < 2 r .
    • За одну операцию мы выбираем наименьшее число последовательности (M) и умножаем его на X = 2 r − (S − M)/M.
  • Выведите элемент, значение которого в массиве минимально.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

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