Максимизируйте общее количество битов элементов в массиве размером N с суммой M

Опубликовано: 19 Сентября, 2022

Имея два целых числа N и M , обозначающие размер массива и сумму элементов массива, задача состоит в том, чтобы найти максимально возможное количество битов общего набора всех элементов массива, так что сумма элементов равна М .

Примеры:

Input: N = 1, M = 15
Output: 4
Explanation: Since N =1, 15 is the only possible solution. 
The binary representation of 15 is (1111)2 which has 4 set bits.

Input: N = 2, M = 11
Output: 4
Explanation: There can be various options for the vector of size 2 and sum 11.
For example: [1, 10] this will give the set bits as 1 + 2 = 3 
as their binary representations are 1 and 1010 respectively.
Similarly [2, 9] and [3, 8] will also give 3 set bits 
as their binary representations are [10, 1001] and [11, 1000] respectively.
For [4, 7] the set bits will be maximum as 
4 is represented by 100 and 7 is represented by 111.
So the total count of set bits = 1 + 3 =4.
Similarly [5, 6] is also a possible solution which gives sum of set bits 4.
For any other options the sum of set bits is always less than 4. 
Hence the maximum number of set bits achieved is 4.

Подход: Эта проблема может быть решена с помощью концепции паритета и жадного подхода, основанного на следующей идее:

To maximize the set bit it is optimal to choose as small numbers as possible and set as many bits in each position as possible.

  • Put as many 1s as feasible at the current bit for each bit from lowest to highest. 
  • However, if the parity of M and N differs, we won’t be able to put N 1s on that bit since we won’t be able to achieve M as the sum no matter how we set the upper bits. 
  • Hence we find out the minimum of N and M (say cur) and then compare the parity of cur and M. 
    If their parity is different we decrease the cur value by 1 to match the parity of M and set that many bits to 1.

Then adjust the sum M, by dividing it by 2 (For easy calculation in next step. We will only need to check the rightmost position and each set bit will contribute 1 to the sum) and repeat this till M becomes 0.

Следуйте приведенной ниже иллюстрации для лучшего понимания:

Иллюстрация:

Consider N = 2 and M = 11.

1st Step:
        => Minimum of 2 and 11 = 2. So cur = 2
        => cur is even and M is odd. Decrease cur by 1. So cur = 2 – 1 = 1.
        => Set 1 bit. So, M = 10, ans = 1.
        => Change M = M/2 = 

2nd Step:
        => Minimum of 2 and 5 = 2. So cur = 2
        => cur is even and M is odd. Decrease cur by 1. So cur = 2 – 1 = 1.
        => Set 1 bits. So, M = 5 – 1 = 4, ans = 1 + 1 = 2.
        => Set M = 4/2 = 2.

3rd Step:
        => Minimum of 2 and 2 = 2. So cur = 2
        => cur is even and M is also even.
        => Set 2 bits. So, M = 2 – 2 = 0, ans = 2 + 2 = 4.
        => Set M = 0/2 = 0.

Для реализации подхода выполните следующие шаги:

  • Инициализируйте переменные, чтобы сохранить минимум на каждом шаге и ответе.
  • Повторяйте цикл до тех пор, пока M не станет больше 0:
    • Найдите минимум M и N .
    • Найдите количество битов, которые нужно установить, используя приведенное выше наблюдение.
    • Отрегулируйте M соответственно, как указано выше.
    • Добавьте количество битов, установленных на этом этапе.
  • В конце верните общее количество битов в качестве требуемого ответа.

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

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

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