Untitled

 avatar
unknown
c_cpp
15 days ago
1.1 kB
11
Indexable
int getMinimumAlterations(string server_health) {
    int n = server_health.size();
    if (n < 3) return 0;
    
    // Case 1: all 0s or all 1s
    int count0 = 0, count1 = 0;
    for (char c : server_health) {
        if (c == '0') count0++;
        else count1++;
    }
    int min_flips = min(count0, count1);
    
    // Case 2: 0s followed by 1s
    vector<int> prefix0(n + 1, 0), prefix1(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix0[i + 1] = prefix0[i] + (server_health[i] == '0' ? 0 : 1);
        prefix1[i + 1] = prefix1[i] + (server_health[i] == '1' ? 0 : 1);
    }
    
    // For 0s followed by 1s: find the best split point i where 0..i are 0s and i+1..n-1 are 1s
    for (int i = 0; i <= n; ++i) {
        int flips = prefix0[i] + (prefix1[n] - prefix1[i]);
        if (flips < min_flips) {
            min_flips = flips;
        }
    }
    
    // Case 3: 1s followed by 0s
    for (int i = 0; i <= n; ++i) {
        int flips = prefix1[i] + (prefix0[n] - prefix0[i]);
        if (flips < min_flips) {
            min_flips = flips;
        }
    }
    
    return min_flips;
}
Editor is loading...
Leave a Comment