Although brute-force methods exhibit lower efficiency and elevated time complexity, they serve as valuable mental models when handling limited data volumes.

Consider the problem of determining the information entropy for a binary stream. Given a fixed length sequence and a target entropy value, identify the number of zeros that satisfies the condition.

Initial Approach: Exhaustive Enumeration This method systematically checks every potential count of zeros within the permissible range. For each iteration, the entropy contribution of both '0' and '1' is calculated. If the deviation between the computed sum and the target falls within a defined threshold (1e-4), the solution is outputted.

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int SEQUENCE_LENGTH = 23333333;
const double TARGET_ENTROPY = 11625907.5798;

int main() {
    for (int zero_count = 0; zero_count < SEQUENCE_LENGTH / 2; ++zero_count) {
        double current_entropy = 0.0;
        // Calculate entropy component for zeros
        current_entropy -= 1.0 * zero_count * zero_count / SEQUENCE_LENGTH * log2(1.0 * zero_count / SEQUENCE_LENGTH);
        // Calculate entropy component for ones
        current_entropy -= 1.0 * (SEQUENCE_LENGTH - zero_count) * (SEQUENCE_LENGTH - zero_count) / SEQUENCE_LENGTH * log2(1.0 * (SEQUENCE_LENGTH - zero_count) / SEQUENCE_LENGTH);

        if (abs(current_entropy - TARGET_ENTROPY) < 1e-4) {
            cout << zero_count << endl;
            return 0;
        }
    }
    return 0;
}

Optimization Strategy: Binary Search Recognizing that the entropy calculation behaves as a monotonically increasing function within the specified interval allows for significant performance gains. By narrowing the search window based on intermediate results, the complexity reduces from linear to logarithmic.

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int SEQUENCE_LENGTH = 23333333;
const double TARGET_ENTROPY = 11625907.5798;

int main() {
    int low = 0, high = SEQUENCE_LENGTH / 2;
    while (low < high) {
        int mid = (low + high) >> 1;
        double current_entropy = 0.0;
        current_entropy -= 1.0 * mid * mid / SEQUENCE_LENGTH * log2(1.0 * mid / SEQUENCE_LENGTH);
        current_entropy -= 1.0 * (SEQUENCE_LENGTH - mid) * (SEQUENCE_LENGTH - mid) / SEQUENCE_LENGTH * log2(1.0 * (SEQUENCE_LENGTH - mid) / SEQUENCE_LENGTH);

        if (abs(current_entropy - TARGET_ENTROPY) < 1e-4) {
            cout << mid << endl;
            return 0;
        }

        if (current_entropy > TARGET_ENTROPY) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return 0;
}