Given a positive integer N and an array arr[] consisting of K integers and consider a binary string(say S) having N set bits, the task is to find the average value of the count of set bits after performing over all possible choices of K operations on the string S such that in the ith operation, any of the arr[i] bits out of N bits can be flipped.
Example:
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
Approach: The given problem can be solved using some basic principles of Probability. Suppose, after the (i – 1)th operation, the value of the average number of set bits is p, and the value of the average number of off bits is q. It can be observed that the value of p after the ith operation will become p = p + the average number of off bits flipped into set bits – the average number of set bits flipped into off bits. Since the probability of choosing the bits in the string is equally likely, the value of p can be calculated as pi = pi-1 + q(i – 1)*(arr[i] / N) – p(i – 1)*(arr[i] / N). Follow the steps below to solve the given problem:
- Initialize two variables, say p and q and initially, p = N and q = 0 as all the bits are set bits in the string initially.
- Traverse the given array arr[] using a variable i and update the value of p and q as follows:
- The value of p = p + q*(arr[i] / N) – p*(arr[i] / N).
- Similarly, the value of q = q + p*(arr[i] / N) – q*(arr[i] / N).
- The value stored in p is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the average number// of Set bits after given operationsdouble 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 Codeint 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
// Java program for the above approachimport java.io.*;class GFG { // Function to calculate the average number // of Set bits 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. |
Python3
# Python 3 program for the above approach# Function to calculate the average number# of Set bits after given operationsdef 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 Codeif __name__ == "__main__": N = 5 arr = [1, 2, 3] K = len(arr) print("%.2f" % averageSetBits(N, K, arr)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;public class GFG { // Function to calculate the average number // of Set bits 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 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate the average number // of Set bits 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> |
Output:
2.44
Time Complexity: O(K), as we are using a loop to traverse N times so it will cost us O(K) time
Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
