Valor promedio del conteo de bits establecido en una string binaria dada después de realizar todas las opciones posibles de K operaciones

Dado un entero positivo N y una array arr[] que consiste en K enteros y considere una string binaria (digamos S ) que tiene N bits establecidos, la tarea es encontrar el valor promedio del conteo de bits establecidos después de realizar todas las opciones posibles de K operaciones en la string S tales que en la i ^-ésima operación, cualquiera de los bits arr[i] de N bits se puede voltear.

Ejemplo:

Entrada: N = 3, arr[] = {2, 2}
Salida: 1.6667
Explicación: La string binaria dada que tiene N bits establecidos, digamos S = ‘ 111 ‘. Toda la secuencia posible de movimientos es la siguiente:

• En el primer movimiento volteando los bits S[0] y S[1]. La string será ‘ 001 ‘
  • En el segundo movimiento, volteando los bits S[0] y S[1]. La string será ‘111’ .
  • En el segundo movimiento, invierta los bits S[1] y S[2]. La string será ‘ 010 ‘.
  • En el segundo movimiento, invierta los bits S[0] y S[2]. La string será ‘ 100 ‘.
• En el primer movimiento volteando los bits S[1] y S[2]. La string será ‘ 100 ‘.
  • En el segundo movimiento, volteando los bits S[0] y S[1]. La string será ‘ 010 ‘.
  • En el segundo movimiento, invierta los bits S[1] y S[2]. La string será ‘ 111′ .
  • En el segundo movimiento, invierta los bits S[0] y S[2]. La string será ‘ 001 ‘.
• En el primer movimiento volteando los bits S[0] y S[2]. La string será ‘ 010 ‘.
  • En el segundo movimiento, volteando los bits S[0] y S[1]. La string será ‘ 100 ‘.
  • En el segundo movimiento, invierta los bits S[1] y S[2]. La string será ‘ 001 ‘.
  • En el segundo movimiento, invierta los bits S[0] y S[2]. La string será ‘ 111 ‘.

Por lo tanto, el número total de operaciones distintas posibles es 9 y la cuenta de bits establecidos después de las operaciones en todos los casos es 15. Entonces, el valor promedio será 15/9 = 1.6667.

Entrada: N = 5, arr[] = {1, 2, 3}
Salida: 2,44

Enfoque: El problema dado se puede resolver usando algunos principios básicos de Probabilidad . Suponga que, después de la operación (i – 1) ^-ésima , el valor del número promedio de bits activados es p , y el valor del número promedio de bits desactivados es q . Se puede observar que el valor de p después de la i ^-ésima operación se convertirá en p = p + el número promedio de bits desactivados convertidos en bits establecidos, el número promedio de bits establecidos convertidos en bits desactivados. Dado que la probabilidad de elegir los bits en la string es igualmente probable, el valor de p se puede calcular como p _i = p _i-1 + q_{(i – 1)} *(arr[i] / N) – p _{(i – 1)} *(arr[i] / N) . Siga los pasos a continuación para resolver el problema dado:

• Inicialice dos variables, digamos p y q e inicialmente, p = N y q = 0 , ya que todos los bits se establecen inicialmente en la string.
• Recorra la array dada arr[] usando una variable i y actualice el valor de p y q de la siguiente manera:
  • El valor de p = p + q*(arr[i] / N) – p*(arr[i] / N) .
  • De manera similar, el valor de q = q + p*(arr[i] / N) – q*(arr[i] / N) .
• El valor almacenado en p es la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the average number
// of Set bits after after given operations
double averageSetBits(int N, int K, int arr[])
{
    // Stores the average number of set
    // bits after current operation
    double p = N;
 
    // Stores the average number of set
    // bits after current operation
    double q = 0;
 
    // Iterate through the array arr[] and
    // update the values of p and q
 
    for (int i = 0; i < K; i++) {
 
        // Store the value of p and q of the
        // previous state before their updation
        double _p = p, _q = q;
 
        // Update average number of set bits
        // after performing the ith operation
        p = _p - _p * arr[i] / N + _q * arr[i] / N;
 
        // Update average number of off bits
        // after performing the ith operation
        q = _q - _q * arr[i] / N + _p * arr[i] / N;
    }
 
    // Return Answer
    return p;
}
 
// Driver Code
int main()
{
    int N = 5;
    int arr[] = { 1, 2, 3 };
    int K = sizeof(arr) / sizeof(arr[0]);
 
    cout << setprecision(10)
         << averageSetBits(N, K, arr);
 
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to calculate the average number
    // of Set bits after after given operations
    static double averageSetBits(int N, int K, int arr[])
    {
        // Stores the average number of set
        // bits after current operation
        double p = N;
 
        // Stores the average number of set
        // bits after current operation
        double q = 0;
 
        // Iterate through the array arr[] and
        // update the values of p and q
 
        for (int i = 0; i < K; i++) {
 
            // Store the value of p and q of the
            // previous state before their updation
            double _p = p, _q = q;
 
            // Update average number of set bits
            // after performing the ith operation
            p = _p - _p * arr[i] / N + _q * arr[i] / N;
 
            // Update average number of off bits
            // after performing the ith operation
            q = _q - _q * arr[i] / N + _p * arr[i] / N;
        }
 
        // Return Answer
        return p;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        int arr[] = { 1, 2, 3 };
        int K = arr.length;
 
        System.out.println(String.format(
            "%.10f", averageSetBits(N, K, arr)));
    }
}
 
// This code is contributed by Dharanendra L V.

# Python 3 program for the above approach
 
# Function to calculate the average number
# of Set bits after after given operations
def averageSetBits(N, K, arr):
 
    # Stores the average number of set
    # bits after current operation
    p = N
 
    # Stores the average number of set
    # bits after current operation
    q = 0
 
    # Iterate through the array arr[] and
    # update the values of p and q
 
    for i in range(K):
 
        # Store the value of p and q of the
        # previous state before their updation
        _p = p
        _q = q
 
        # Update average number of set bits
        # after performing the ith operation
        p = _p - _p * arr[i] / N + _q * arr[i] / N
 
        # Update average number of off bits
        # after performing the ith operation
        q = _q - _q * arr[i] / N + _p * arr[i] / N
 
    # Return Answer
    return p
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    arr = [1, 2, 3]
    K = len(arr)
 
    print("%.2f" % averageSetBits(N, K, arr))
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
 
public class GFG {
 
    // Function to calculate the average number
    // of Set bits after after given operations
    static double averageSetBits(int N, int K, int []arr)
    {
       
        // Stores the average number of set
        // bits after current operation
        double p = N;
 
        // Stores the average number of set
        // bits after current operation
        double q = 0;
 
        // Iterate through the array []arr and
        // update the values of p and q
 
        for (int i = 0; i < K; i++) {
 
            // Store the value of p and q of the
            // previous state before their updation
            double _p = p, _q = q;
 
            // Update average number of set bits
            // after performing the ith operation
            p = _p - _p * arr[i] / N + _q * arr[i] / N;
 
            // Update average number of off bits
            // after performing the ith operation
            q = _q - _q * arr[i] / N + _p * arr[i] / N;
        }
 
        // Return Answer
        return p;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 5;
        int []arr = { 1, 2, 3 };
        int K = arr.Length;
 
        Console.WriteLine(String.Format(
            "{0:F10}", averageSetBits(N, K, arr)));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
       // JavaScript Program to implement
       // the above approach
 
       // Function to calculate the average number
       // of Set bits after after given operations
       function averageSetBits(N, K, arr)
       {
        
           // Stores the average number of set
           // bits after current operation
           let p = N;
 
           // Stores the average number of set
           // bits after current operation
           let q = 0;
 
           // Iterate through the array arr[] and
           // update the values of p and q
 
           for (let i = 0; i < K; i++) {
 
               // Store the value of p and q of the
               // previous state before their updation
               let _p = p, _q = q;
 
               // Update average number of set bits
               // after performing the ith operation
               p = _p - _p * arr[i] / N + _q * arr[i] / N;
 
               // Update average number of off bits
               // after performing the ith operation
               q = _q - _q * arr[i] / N + _p * arr[i] / N;
           }
 
           // Return Answer
           return p;
       }
 
       // Driver Code
       let N = 5;
       let arr = [1, 2, 3];
       let K = arr.length;
 
       document.write(averageSetBits(N, K, arr).toPrecision(3));
 
    // This code is contributed by Potta Lokesh
   </script>

2.44

 Complejidad de tiempo: O(K), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(K) tiempo 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.