Skip to content

1000 Rated problems

  1. Binary String Transformation Problem
  2. Minimum Operations to Make Product Divisible by k

Binary String Transformation Problem

Problem link on codeforces

Problem Statement

Given a binary string s, transform it into a "good" string t where every position differs from the original string (t[i] ≠ s[i]).

Available operations:

  • Delete a character (cost: 1 coin)
  • Swap any two characters (cost: 0 coins)

Goal: Find the minimum cost to create a good string.

Solution Approach

Key Insight

Since swaps are free, we can rearrange characters at no cost. The optimal strategy is to:

  1. Swap characters to maximize positions where t[i] ≠ s[i]
  2. Delete excess characters that cannot be repositioned

Algorithm Logic

The solution uses a greedy matching approach:

For each position i in the original string:
  - If s[i] = '1', try to place a '0' at position i
  - If s[i] = '0', try to place a '1' at position i
  - Track remaining available 0s and 1s

Special Cases

  1. Single character → Must delete it (cost: 1)
  2. Equal 0s and 1s → Perfect swap exists (cost: 0)
  3. Only 0s or only 1s → Must delete all (cost: n)

Core Implementation

int zeros = count('0');
int ones = count('1');

// Greedy assignment
for each character c in s:
    if c == '1':
        use a '0' → zeros--
    else:
        use a '1' → ones--

    if ran out of needed characters:
        remaining positions must be deleted
        break

Code

void solve() {
    string s; cin >> s;
    if (s.size() == 1) {
        std::cout << 1 << "\n"; return;
    }

    int zeros = 0;
    int ones = 0;
    for (auto c : s) {
        if (c == '0') {
            zeros++;
        } else {
            ones++;
        }
    }

    if (zeros == ones) {
        std::cout << 0 << "\n"; return;
    }

    if (zeros == 0 or ones == 0) {
        std::cout << s.size() << "\n"; return;
    }

    int t = 0;
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (c == '1') {
            t++; zeros--;
            if (zeros < 0) {
                t--;
                std::cout << s.size() - t << "\n"; return;
            }
        } else if (c == '0') {
            t++; ones--;
            if (ones < 0) {
                t--;
                std::cout << s.size() - t << "\n"; return;
            }
        }
    }
}

Complexity

  • Time: O(n) - only pass twice through the string
  • Space: O(1) - only counters needed

Example Walkthrough

Input: s = "1100"

  • Initial: zeros = 2, ones = 2
  • Position 0: s[0] = '1' → use '0' (zeros = 1) ✓
  • Position 1: s[1] = '1' → use '0' (zeros = 0) ✓
  • Position 2: s[2] = '0' → use '1' (ones = 1) ✓
  • Position 3: s[3] = '0' → use '1' (ones = 0) ✓

Result: t = "0011", cost = 0 (perfect swap)

Input: s = "111000"

  • Initial: zeros = 3, ones = 3
  • Positions 0-2: consume all 3 zeros
  • Positions 3-5: consume all 3 ones

Result: cost = 0

Input: s = "11100"

  • Initial: zeros = 2, ones = 3
  • Position 0-1: use 2 zeros (zeros = 0)
  • Position 2: need zero but none left → stop
  • Successfully placed: 2 characters
  • Must delete: 5 - 2 = 3 characters

Result: cost = 3

Minimum Operations to Make Product Divisible by k

1. Problem Summary

Given an array of n integers and a number k (2 ≤ k ≤ 5), find the minimum number of operations needed to make the product of all array elements divisible by k. In each operation, you can increment any element by 1.

Input/Output Format: - Input: Integer n (array size), integer k (divisor), followed by n integers - Output: Minimum number of operations required

Key Constraints: - 2 ≤ k ≤ 5 (k can only be 2, 3, 4, or 5) - 1 ≤ n ≤ 10^5 - This limited range of k is crucial for the solution approach

2. Approach & Intuition

Key Insight: The product a₁ · a₂ · ... · aₙ is divisible by k if and only if the product contains all prime factors of k with sufficient multiplicity.

Why This Works: - For k = 2, 3, 5 (primes): We need at least one element divisible by k - For k = 4 = 2²: We need either one element divisible by 4, OR two elements divisible by 2

Strategy: 1. Check if any element is already divisible by k → answer is 0 2. For k = 4, handle special case: count even numbers to determine if we can get two factors of 2 3. Otherwise, find the minimum operations needed to make any single element divisible by k

3. Algorithm Breakdown

Step-by-Step:

  1. Early Exit Check: If any element is divisible by k, return 0
  2. Calculate Minimum Gap: For each element, calculate (k - (a[i] % k)) % k - the operations needed to make it divisible by k
  3. Special Handling for k = 4:
  4. Count even numbers in the array
  5. If n = 1: Use the minimum gap
  6. If no even numbers: Compare min(2, min_gap) - we can make one number even twice
  7. If 1 even number: Compare min(1, min_gap) - we need one more even
  8. If ≥2 even numbers: Already divisible (shouldn't reach here due to step 1)
  9. For k = 2, 3, 5: Return the minimum gap

Time Complexity: O(n) - Single pass through the array to read input and calculate minimum gap - All operations are O(1) per element

Space Complexity: O(n) - Storing the array of n elements - Could be optimized to O(1) by not storing the array

4. Code Walkthrough

void solve() {
    int n, k, min_far = INT_MAX; 
    cin >> n >> k; 
    bool flag = false;
    int even = 0;

    // Read array and calculate metrics
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (!(a[i] & 1)) even++;  // Count even numbers for k=4 case

        // Calculate operations needed to make a[i] divisible by k
        min_far = min(min_far, (k - (a[i]%k))%k);

        // Early exit flag if already divisible
        if (a[i] % k == 0) {
            flag = true;
        }
    }

    // Already divisible
    if (flag) {
        cout << "0\n"; return;
    }

    // Special case: k = 4 requires two factors of 2
    if (k == 4) {
        if (n == 1) { 
            // Single element: must make it divisible by 4
            cout << min_far << "\n"; return;
        } else if (even == 0) {
            // No even numbers: either make one divisible by 4, 
            // or make two numbers even (2 operations)
            cout << min(2, min_far) << "\n";
        } else if (even == 1) {
            // One even number: need one more factor of 2
            // Either make another number even (1 op) or make one divisible by 4
            cout << min(1, min_far) << "\n";
        } else if (even >= 2) {
            // Two or more even numbers: product has at least 2² = 4
            cout << 0 << "\n";
        }
        return;
    }

    // For k = 2, 3, 5: just need one element divisible by k
    cout << min_far << "\n";
}

Critical Sections:

  • (k - (a[i]%k))%k: Handles the case when a[i] % k == 0 elegantly (gives 0)
  • !(a[i] & 1): Bitwise check for even numbers (faster than a[i] % 2 == 0)
  • k = 4 logic: Recognizes that 4 = 2² needs two factors of 2, which can come from two even numbers OR one multiple of 4

Test Cases

Example Walkthrough: 

Input: n=3, k=4, array=[2, 3, 5]
- a[0]=2: not divisible by 4, gap = (4-2)%4 = 2
- a[1]=3: not divisible by 4, gap = (4-3)%4 = 1
- a[2]=5: not divisible by 4, gap = (4-1)%4 = 3
- min_far = 1
- even = 1 (only a[0]=2)
- Since k=4 and even=1: answer = min(1, 1) = 1
- Incrementing a[1] once gives [2, 4, 5], product = 40 divisible by 4 ✓

Edge Cases:

  1. Already divisible: k=3, array=[6, 9] → Output: 0
  2. Single element: k=4, array=[7] → Output: 1 (make it 8)
  3. k=4 with no evens: k=4, array=[1, 3, 5] → Output: 2
  4. k=4 with 2+ evens: k=4, array=[2, 4, 6] → Output: 0
  5. Prime k: k=5, array=[3, 7, 11] → Output: 2 (make 3→5)

Comments

This comments system is powered by GitHub Discussions