search
HomeBackend DevelopmentC++The average of the set bit counts in a given binary string after all possible K operations

The average of the set bit counts in a given binary string after all possible K operations

In this problem, we need to find the average of the set bit count after performing all selected K operations on the given string.

Brute force methods can be used to solve the problem, but we will use probability principles to overcome the time complexity of brute force methods.

Problem Statement - We are given an integer N, an array arr[] containing K positive integers, and a binary string of length N containing only set bits. We need to find the average of the set bit count after performing all possible K operations. In the i-th operation, we can flip any arr[i] bit in the given string.

Example

Input– N = 2, arr[] = {1, 2}

Output– 1

Description – The initial binary string is 11.

  • In the first step, we can flip the first character and the string will be 01.

    • In the second operation, we need to flip any two bits. So the string will become 10.

  • The second selection can start by flipping the second character from the first step and the string will be 10.

    • In the second step of the current operation, we need to flip any 2 bits, and the string can be 01.

So, we have two choices, the final string can be 01 or 10.

Total selections = 2, total set bits in final string = 2, ans = 2/2 = 1.

Input– N = 3, arr[] = {2, 2}

Output– 1.6667

Explanation – We have an initial string which is 111.

  • In the first operation, we can flip any 2 characters. So the string could be 001, 100, 010.

  • In the second operation, we can flip 2 bits in the resulting string from the first operation.

    • When we flip any two bits of 001, we get 111, 010 and 100.

    • When we flip any 2 digits of 100, we can get 010, 111 and 001.

    • When we flip any two bits of 010, we can get 100, 001 and 111.

So, in the last operation, we got a total of 9 different strings.

The total number of setting digits in 9 strings=15, the total number of operations=9, the answer=15/9=1.6667

method one

Here, we will use the principle of probability to solve this problem. Suppose that after performing i-1 operations, the average value of the set bits is p and the average value of the unset bits is q. We need to calculate the average of the set bits and unset bits in the ith operation.

So, the updated value of p can be the average of the new set bits of p - the average of the new closed bits.

algorithm

  • Initialize P to N because we initially have N set bits, and initialize Q to 0 because we initially have 0 set bits.

  • Traverse the operation array.

  • Initialize prev_p and prev_q using P and Q values.

  • Update the P value using prev_p - prev_p * arr[i] / N prev_q * arr[i] / N, which will average the inverted bits to the set bits and average the set bits Invert to unset bits

  • Update Q value.

  • Return P value.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;

double getAverageBits(int len, int K, int array[]) {
   // to store the average '1's in the binary string
   double P = len;
   // to store the average '0's in the binary string
   double Q = 0;
   // Traverse the array array[]
   for (int i = 0; i < K; i++) {
      // Initialize the prev_p and prev_q with P and Q, which we got from the previous iteration
      double prev_p = P, prev_q = Q;
      // Update the average '1's
      P = prev_p - prev_p * array[i] / len + prev_q * array[i] / len;
      // Update the average '0's
      Q = prev_q - prev_q * array[i] / len + prev_p * array[i] / len;
   }
   return P;
}
int main() {
   int N = 2;
   int array[] = {1};
   int K = sizeof(array) / sizeof(array[0]);
   cout << "The average number of set bits after performing the operations is " << getAverageBits(N, K, array);
   return 0;
}

Output

The average number of set bits after performing the operations is 1

Time complexity - O(K), where K is the length of the array.

Space Complexity - O(1) since we are not using any extra space.

In this tutorial we learned to find the average set bit after performing all possible choices of K operations. In single selection we need to perform all the operations given in the array.

The above is the detailed content of The average of the set bit counts in a given binary string after all possible K operations. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
C   XML Frameworks: Choosing the Right One for YouC XML Frameworks: Choosing the Right One for YouApr 30, 2025 am 12:01 AM

The choice of C XML framework should be based on project requirements. 1) TinyXML is suitable for resource-constrained environments, 2) pugixml is suitable for high-performance requirements, 3) Xerces-C supports complex XMLSchema verification, and performance, ease of use and licenses must be considered when choosing.

C# vs. C  : Choosing the Right Language for Your ProjectC# vs. C : Choosing the Right Language for Your ProjectApr 29, 2025 am 12:51 AM

C# is suitable for projects that require development efficiency and type safety, while C is suitable for projects that require high performance and hardware control. 1) C# provides garbage collection and LINQ, suitable for enterprise applications and Windows development. 2)C is known for its high performance and underlying control, and is widely used in gaming and system programming.

How to optimize codeHow to optimize codeApr 28, 2025 pm 10:27 PM

C code optimization can be achieved through the following strategies: 1. Manually manage memory for optimization use; 2. Write code that complies with compiler optimization rules; 3. Select appropriate algorithms and data structures; 4. Use inline functions to reduce call overhead; 5. Apply template metaprogramming to optimize at compile time; 6. Avoid unnecessary copying, use moving semantics and reference parameters; 7. Use const correctly to help compiler optimization; 8. Select appropriate data structures, such as std::vector.

How to understand the volatile keyword in C?How to understand the volatile keyword in C?Apr 28, 2025 pm 10:24 PM

The volatile keyword in C is used to inform the compiler that the value of the variable may be changed outside of code control and therefore cannot be optimized. 1) It is often used to read variables that may be modified by hardware or interrupt service programs, such as sensor state. 2) Volatile cannot guarantee multi-thread safety, and should use mutex locks or atomic operations. 3) Using volatile may cause performance slight to decrease, but ensure program correctness.

How to measure thread performance in C?How to measure thread performance in C?Apr 28, 2025 pm 10:21 PM

Measuring thread performance in C can use the timing tools, performance analysis tools, and custom timers in the standard library. 1. Use the library to measure execution time. 2. Use gprof for performance analysis. The steps include adding the -pg option during compilation, running the program to generate a gmon.out file, and generating a performance report. 3. Use Valgrind's Callgrind module to perform more detailed analysis. The steps include running the program to generate the callgrind.out file and viewing the results using kcachegrind. 4. Custom timers can flexibly measure the execution time of a specific code segment. These methods help to fully understand thread performance and optimize code.

How to use the chrono library in C?How to use the chrono library in C?Apr 28, 2025 pm 10:18 PM

Using the chrono library in C can allow you to control time and time intervals more accurately. Let's explore the charm of this library. C's chrono library is part of the standard library, which provides a modern way to deal with time and time intervals. For programmers who have suffered from time.h and ctime, chrono is undoubtedly a boon. It not only improves the readability and maintainability of the code, but also provides higher accuracy and flexibility. Let's start with the basics. The chrono library mainly includes the following key components: std::chrono::system_clock: represents the system clock, used to obtain the current time. std::chron

What is real-time operating system programming in C?What is real-time operating system programming in C?Apr 28, 2025 pm 10:15 PM

C performs well in real-time operating system (RTOS) programming, providing efficient execution efficiency and precise time management. 1) C Meet the needs of RTOS through direct operation of hardware resources and efficient memory management. 2) Using object-oriented features, C can design a flexible task scheduling system. 3) C supports efficient interrupt processing, but dynamic memory allocation and exception processing must be avoided to ensure real-time. 4) Template programming and inline functions help in performance optimization. 5) In practical applications, C can be used to implement an efficient logging system.

How to understand ABI compatibility in C?How to understand ABI compatibility in C?Apr 28, 2025 pm 10:12 PM

ABI compatibility in C refers to whether binary code generated by different compilers or versions can be compatible without recompilation. 1. Function calling conventions, 2. Name modification, 3. Virtual function table layout, 4. Structure and class layout are the main aspects involved.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function