Aggressive Cows Maximum Minimum Distance in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of maximum minimum distance calculation

What is the output of the following C++ code that finds the largest minimum distance to place 3 cows in given stalls?

DSA C++

/*
Stalls positions: 1, 2, 8, 4, 9
Number of cows: 3
*/
#include <iostream>
#include <vector>
#include <algorithm>

bool canPlaceCows(const std::vector<int>& stalls, int cows, int dist) {
    int count = 1; // place first cow at first stall
    int last_position = stalls[0];
    for (int i = 1; i < stalls.size(); i++) {
        if (stalls[i] - last_position >= dist) {
            count++;
            last_position = stalls[i];
            if (count == cows) return true;
        }
    }
    return false;
}

int maxMinDistance(std::vector<int>& stalls, int cows) {
    std::sort(stalls.begin(), stalls.end());
    int low = 1;
    int high = stalls.back() - stalls[0];
    int result = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canPlaceCows(stalls, cows, mid)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    std::vector<int> stalls = {1, 2, 8, 4, 9};
    int cows = 3;
    std::cout << maxMinDistance(stalls, cows) << std::endl;
    return 0;
}

A 3

B 4

C 5

D 2

💡 Hint

Think about binary searching the minimum distance and checking feasibility.

The maximum minimum distance to place 3 cows in stalls at positions 1, 2, 4, 8, 9 is 4. This is because placing cows at positions 1, 4, and 8 or 1, 4, and 9 maintains at least 4 units apart.

🧠 Conceptual

intermediate

Understanding the feasibility check in Aggressive Cows problem

In the Aggressive Cows problem, what does the feasibility function (like canPlaceCows) check?

A If cows can be placed in all stalls without any distance restriction

B If cows can be placed to maximize the total distance sum between them

C If cows can be placed only in consecutive stalls

D If cows can be placed such that the minimum distance between any two cows is at least a given value

💡 Hint

Focus on the minimum distance condition.

The feasibility function checks if it is possible to place all cows in stalls so that the minimum distance between any two cows is at least the given distance.

🔧 Debug

advanced

Identify the bug in this Aggressive Cows implementation

What error does the following code produce when run, and why? #include #include #include bool canPlaceCows(std::vector& stalls, int cows, int dist) { int count = 1; int last_position = stalls[0]; for (int i = 1; i <= stalls.size(); i++) { if (stalls[i] - last_position >= dist) { count++; last_position = stalls[i]; if (count == cows) return true; } } return false; } int main() { std::vector stalls = {1, 2, 4, 8, 9}; std::sort(stalls.begin(), stalls.end()); std::cout << canPlaceCows(stalls, 3, 3) << std::endl; return 0; }

A Compilation error due to missing return statement

B Runs successfully and prints 1

C Throws std::out_of_range exception

D Infinite loop

💡 Hint

Check the loop boundary condition.

The loop uses i <= stalls.size(), which accesses stalls[stalls.size()] causing out_of_range exception.

🚀 Application

advanced

Applying Aggressive Cows logic to a new scenario

You have stalls at positions [10, 20, 30, 40, 50, 60] and want to place 4 cows. What is the maximum minimum distance possible?

A 10

B 15

C 20

D 25

💡 Hint

Try placing cows greedily with binary search on distance.

The maximum minimum distance is 10, placing cows at 10, 20, 40, and 60 or similar positions.

🧠 Conceptual

expert

Why binary search is used in Aggressive Cows problem?

Why is binary search an efficient approach to find the maximum minimum distance in the Aggressive Cows problem?

A Because the search space of possible minimum distances is sorted and monotonic in feasibility

B Because the stalls are sorted and binary search finds the exact stall positions

C Because binary search can directly place cows in optimal positions

D Because it reduces the number of stalls to consider

💡 Hint

Think about how feasibility changes with distance.

The feasibility of placing cows is monotonic: if cows can be placed at distance d, they can be placed at any smaller distance. This allows binary search on distance.