all_zeroes.cpp

#include <iostream>
#include <string>
#include <bitset>

class BinaryManipulation {
public:
    static int minOperations(int n) {
        int operations = 0;
        // Convert the number to its binary representation
        std::string binary = std::bitset<32>(n).to_string();
        // Remove leading zeros
        binary = binary.substr(binary.find_first_not_of('0'));
        int length = binary.length();
        // Iterate until all bits are '0'
        while (!isAllZeros(binary)) {
            // Apply Rule 2 to the rightmost bit
            if (binary[length - 1] == '0') {
                binary[length - 1] = '1'; // Flip 0 to 1
                operations++;
            } else {
                binary[length - 1] = '0'; // Flip 1 to 0
                operations++;
            }
            // Check the other bits for Rule 1
            for (int i = length - 2; i >= 0; i--) {
                // Rule 1: Check if the (i+1)-th bit is 1 and all bits after it are 0
                if (binary[i + 1] == '1' && isAllZerosFrom(binary, i + 2)) {
                    if (binary[i] == '0') {
                        binary[i] = '1'; // Change '0' to '1'
                        operations++;
                        break; // Break and restart the process
                    } else if (binary[i] == '1') {
                        binary[i] = '0'; // Change '1' to '0'
                        operations++;
                        break; // Break and restart the process
                    }
                }
            }
        }
        return operations;
    }

private:
    // Helper function to check if all bits in the binary string are '0'
    static bool isAllZeros(const std::string& binary) {
        for (char c : binary) {
            if (c != '0') {
                return false;
            }
        }
        return true;
    }

    // Helper function to check if all bits from a given index onward are '0'
    static bool isAllZerosFrom(const std::string& binary, int fromIndex) {
        for (int i = fromIndex; i < binary.length(); i++) {
            if (binary[i] != '0') {
                return false;
            }
        }
        return true;
    }
};

int main() {
    // Test case: n = 4 (binary: 100)
    int n = 4;
    std::cout << "Minimum operations to reduce " << n << " to 0: " << BinaryManipulation::minOperations(n) << std::endl;  // Expected output: 7
    return 0;
}