Среднее значение установленного количества битов в заданной двоичной строке после выполнения всех возможных вариантов K операций

Учитывая положительное целое число N и массив arr[] , состоящий из K целых чисел, и рассмотрим двоичную строку (скажем, S ), имеющую N установленных битов, задача состоит в том, чтобы найти среднее значение количества установленных битов после выполнения всех возможных вариантов выбора K операций над строкой S , так что в i ^-й операции любой из битов arr[i] из N битов может быть инвертирован.

Пример:

Input: N = 3, arr[] = {2, 2}
Output: 1.6667
Explanation: The given binary string having N set bits, let’s say S = ‘111‘. All the possible sequence of moves are as follows:

• In the first move flipping bits S[0] and S[1]. The string will be ‘001‘
  • In second move flipping bits S[0] and S[1]. The string will be ‘111’.
  • In second move flipping bits S[1] and S[2]. The string will be ‘010‘.
  • In second move flipping bits S[0] and S[2]. The string will be ‘100‘.
• In the first move flipping bits S[1] and S[2]. The string will be ‘100‘.
  • In second move flipping bits S[0] and S[1]. The string will be ‘010‘.
  • In second move flipping bits S[1] and S[2]. The string will be ‘111′.
  • In second move flipping bits S[0] and S[2]. The string will be ‘001‘.
• In the first move flipping bits S[0] and S[2]. The string will be ‘010‘.
  • In second move flipping bits S[0] and S[1]. The string will be ‘100‘.
  • In second move flipping bits S[1] and S[2]. The string will be ‘001‘.
  • In second move flipping bits S[0] and S[2]. The string will be ‘111‘.

Therefore, the total number of distinct operations possible are 9 and the count of set bits after the operations in all the cases is 15. So, the average value will be 15/9 = 1.6667.

Input: N = 5, arr[] = {1, 2, 3}
Output: 2.44

Подход: Данная проблема может быть решена с использованием некоторых основных принципов теории вероятности. Предположим, что после (i – 1) ^-й операции значение среднего числа установленных битов равно p , а значение среднего числа выключенных битов равно q . Можно заметить, что значение p после i ^-й операции станет равным p = p + среднее количество выключенных битов, перевернутых в установленные биты, – среднее количество заданных битов, преобразованных в выключенные биты. Поскольку вероятность выбора битов в строке равновероятна, значение p можно рассчитать как p _i = p _i-1 + q _{(i – 1)} *(arr[i] / N) – p _{(i – 1)} *(обр[i]/N) . Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте две переменные, скажем, p и q , и изначально p = N и q = 0 , поскольку изначально все биты устанавливаются битами в строке.
• Пройдите по заданному массиву arr[] с помощью переменной i и обновите значения p и q следующим образом:
  • Значение p = p + q*(arr[i]/N) – p*(arr[i]/N) .
  • Точно так же значение q = q + p*(arr[i]/N) – q*(arr[i]/N) .
• Значение, хранящееся в p , является требуемым ответом.

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

Временная сложность: O(K), так как мы используем цикл для прохождения N раз, поэтому это будет стоить нам O(K) времени
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.