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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of maximum minimum distance calculation

What is the output of the following Go code that calculates the maximum minimum distance to place 3 cows in given stalls?

DSA Go

package main
import (
	"fmt"
	"sort"
)

func canPlaceCows(stalls []int, cows int, dist int) bool {
	count := 1
	lastPos := stalls[0]
	for i := 1; i < len(stalls); i++ {
		if stalls[i]-lastPos >= dist {
			count++
			lastPos = stalls[i]
			if count == cows {
				return true
			}
		}
	}
	return false
}

func maxMinDistance(stalls []int, cows int) int {
	sort.Ints(stalls)
	low, high := 0, stalls[len(stalls)-1]-stalls[0]
	result := 0
	for low <= high {
		mid := (low + high) / 2
		if canPlaceCows(stalls, cows, mid) {
			result = mid
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return result
}

func main() {
	stalls := []int{1, 2, 8, 4, 9}
	cows := 3
	fmt.Println(maxMinDistance(stalls, cows))
}

A 2

B 3

C 5

D 4

💡 Hint

Think about placing cows with the largest minimum gap possible using binary search.

The maximum minimum distance to place 3 cows in stalls at positions [1,2,4,8,9] is 3. The cows can be placed at positions 1, 4, and 8.

🧠 Conceptual

intermediate

Understanding the role of sorting in Aggressive Cows problem

Why is it necessary to sort the stall positions before applying the binary search approach in the Aggressive Cows problem?

A To ensure the stalls are in increasing order so we can check distances between adjacent stalls correctly

B Sorting is not necessary; the algorithm works without sorting

C To group stalls with the same position together

D To find the maximum stall position easily

💡 Hint

Think about how distances between stalls are calculated.

Sorting allows us to check distances between stalls in order, which is essential for placing cows with minimum distance constraints.

🔧 Debug

advanced

Identify the bug causing incorrect output

The following Go code attempts to solve the Aggressive Cows problem but returns 2 instead of the correct answer 3. What is the bug?

DSA Go

func canPlaceCows(stalls []int, cows int, dist int) bool {
	count := 1
	lastPos := stalls[0]
	for i := 1; i < len(stalls); i++ {
		if stalls[i]-lastPos > dist {
			count++
			lastPos = stalls[i]
			if count == cows {
				return true
			}
		}
	}
	return false
}

A The lastPos should be initialized to stalls[len(stalls)-1]

B The count should start from 0 instead of 1

C The condition should be stalls[i]-lastPos >= dist instead of > dist

D The loop should start from i = 0 instead of i = 1

💡 Hint

Check the condition that decides if a cow can be placed at a stall.

Using > dist excludes cases where the distance equals dist, which is valid placement. Changing to >= fixes the bug.

❓ Predict Output

advanced

Output of maximum minimum distance with larger input

What is the output of the following Go code that calculates the maximum minimum distance to place 4 cows in given stalls?

DSA Go

package main
import (
	"fmt"
	"sort"
)

func canPlaceCows(stalls []int, cows int, dist int) bool {
	count := 1
	lastPos := stalls[0]
	for i := 1; i < len(stalls); i++ {
		if stalls[i]-lastPos >= dist {
			count++
			lastPos = stalls[i]
			if count == cows {
				return true
			}
		}
	}
	return false
}

func maxMinDistance(stalls []int, cows int) int {
	sort.Ints(stalls)
	low, high := 0, stalls[len(stalls)-1]-stalls[0]
	result := 0
	for low <= high {
		mid := (low + high) / 2
		if canPlaceCows(stalls, cows, mid) {
			result = mid
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return result
}

func main() {
	stalls := []int{1, 2, 4, 8, 9, 12, 16}
	cows := 4
	fmt.Println(maxMinDistance(stalls, cows))
}

A 5

B 7

C 6

D 4

💡 Hint

Try placing cows with increasing minimum distances and check feasibility.

The largest minimum distance to place 4 cows in stalls [1,2,4,8,9,12,16] is 4. One placement is at 1, 8, 12, and 16.

🧠 Conceptual

expert

Why binary search is suitable for Aggressive Cows problem?

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

A Because the problem can be transformed into a decision problem where feasibility of a distance can be checked in linear time

B Because sorting the stalls automatically gives the answer without further checks

C Because the number of cows is always small, so binary search is faster

D Because binary search directly finds the exact stall positions for cows

💡 Hint

Think about how binary search narrows down the search space using a yes/no check.

Binary search efficiently narrows down the maximum minimum distance by checking if cows can be placed with a given distance, which is a yes/no decision problem.