Bulls And Cows Solution for Google
Company: Google · Difficulty: Hard · Topics: String, Hash Table, Counting
Problem Statement
You are playing the Bulls and Cows game with your friend. You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
- The number of "bulls", which are digits in the guess that are in the correct position.
- The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position.
Key Understanding:
- Bulls are digits that match both in value and position
- Cows are digits that exist in the secret but are in wrong positions
- Both secret and guess may contain duplicate digits
- We need to count bulls first, then count cows from remaining digits
- The hint format is "xAyB" where x = bulls, y = cows
Examples
Example 1:
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation:
- Bulls: 8 is in the correct position (index 2)
- Cows: 1, 0, and 7 are in the secret but in wrong positions
- Visual representation:
```
Secret: 1 8 0 7
Guess: 7 8 1 0
Result: C B C C (B=Bull, C=Cow)
```
Example 2:
Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation:
- Bulls: 1 is in the correct position (index 2)
- Cows: 1 is in the secret but in wrong position
- Visual representation:
```
Secret: 1 1 2 3
Guess: 0 1 1 1
Result: C C B C (B=Bull, C=Cow)
```
Example 3:
Input: secret = "1234", guess = "5678"
Output: "0A0B"
Explanation:
- No bulls or cows - no digits match
- Visual representation:
```
Secret: 1 2 3 4
Guess: 5 6 7 8
Result: X X X X (X=No match)
```
Example 4:
Input: secret = "1234", guess = "1234"
Output: "4A0B"
Explanation:
- All digits are bulls (perfect match)
- Visual representation:
```
Secret: 1 2 3 4
Guess: 1 2 3 4
Result: B B B B (B=Bull)
```
Intuition
The key insight is to process the digits in two phases: first count bulls (exact matches), then count cows from the remaining unmatched digits.
Core Concept:
- Bulls are easy to count - just compare digits at same positions
- For cows, we need to count remaining digits that exist in both strings
- We must handle duplicates carefully - each digit can only be used once
Why Two-Phase Approach Works:
- First phase: Count exact matches (bulls) and mark them as used
- Second phase: Count remaining digits that exist in both strings (cows)
- This ensures we don't double-count digits
Mathematical Insight:
- Total matches = bulls + cows
- Bulls are position-dependent matches
- Cows are value-dependent matches (ignoring position)
- We need to track frequency of each digit
Approach
Approach 1: Two-Pass Hash Table (Optimal)
Algorithm:
1. First pass: Count bulls and create frequency maps
2. For each position, if digits match, increment bulls
3. If digits don't match, add to frequency maps
4. Second pass: Count cows from frequency maps
5. For each digit in guess frequency map, add min(freq_secret, freq_guess) to cows
6. Return formatted string
Why This Works:
- We handle bulls and cows separately
- Frequency maps track remaining unmatched digits
- We use minimum frequency to avoid double-counting
- This handles duplicates correctly
Complexity Analysis:
- Time: O(n) - Two passes through the strings
- Space: O(1) - Fixed size arrays for digit frequencies
Approach 2: Single Pass with Array
Algorithm:
1. Use arrays to track digit frequencies
2. In single pass, count bulls and update frequencies
3. Calculate cows from frequency arrays
4. Return formatted string
Why This Works:
- More efficient with single pass
- Uses arrays instead of hash maps
- Still handles duplicates correctly
Complexity Analysis:
- Time: O(n) - Single pass through the strings
- Space: O(1) - Fixed size arrays
Approach 3: Brute Force
Algorithm:
1. Count bulls by comparing positions
2. For each unmatched digit in guess, check if it exists in secret
3. Count cows manually
4. Return formatted string
Why This Works:
- Simple and straightforward
- Easy to understand and implement
- Less efficient but correct
Complexity Analysis:
- Time: O(n²) - For each guess digit, scan secret
- Space: O(1) - Constant extra space
Dry Run
Let's trace through Example 1: secret = "1807", guess = "7810"
Two-Pass Hash Table Approach:
Step 1: Initialize
- bulls = 0
- secretFreq = [0,0,0,0,0,0,0,0,0,0]
- guessFreq = [0,0,0,0,0,0,0,0,0,0]
Step 2: First pass - Count bulls
- i=0: secret[0]='1', guess[0]='7' → No match, add to freq
- secretFreq[1]++, guessFreq[7]++
- i=1: secret[1]='8', guess[1]='8' → Match! bulls++
- bulls = 1
- i=2: secret[2]='0', guess[2]='1' → No match, add to freq
- secretFreq[0]++, guessFreq[1]++
- i=3: secret[3]='7', guess[3]='0' → No match, add to freq
- secretFreq[7]++, guessFreq[0]++
Step 3: Second pass - Count cows
- secretFreq = [1,1,0,0,0,0,0,1,0,0]
- guessFreq = [1,1,0,0,0,0,0,1,0,0]
- cows = min(1,1) + min(1,1) + min(1,1) = 1 + 1 + 1 = 3
Step 4: Return result
- Result = "1A3B"
Single Pass Array Approach:
Step 1: Initialize arrays
- secretCount = [0,0,0,0,0,0,0,0,0,0]
- guessCount = [0,0,0,0,0,0,0,0,0,0]
Step 2: Single pass
- i=0: '1' vs '7' → No match, count[1]++, count[7]++
- i=1: '8' vs '8' → Match! bulls++
- i=2: '0' vs '1' → No match, count[0]++, count[1]++
- i=3: '7' vs '0' → No match, count[7]++, count[0]++
Step 3: Calculate cows
- cows = sum(min(secretCount[i], guessCount[i])) = 3
Step 4: Return "1A3B"
Key Insights
1. Two-Phase Processing: Count bulls first, then cows
2. Frequency Tracking: Use arrays to track digit frequencies
3. Duplicate Handling: Each digit can only be used once
4. Position vs Value: Bulls care about position, cows only care about value
5. Minimum Frequency: Use min(freq1, freq2) to avoid double-counting
Edge Cases
1. Perfect Match: All digits are bulls
2. No Match: No bulls or cows
3. Duplicate Digits: Handle multiple occurrences of same digit
4. Single Digit: Strings of length 1
5. All Same Digits: Strings with all identical digits
6. Empty Strings: Handle edge cases (though constraints prevent this)
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Two-Pass Hash Table (Optimal)
Time Complexity: O(n) - Two passes through the strings
Space Complexity: O(1) - Fixed size arrays for digit frequencies
Advantages:
- Clear separation of bulls and cows counting
- Handles duplicates correctly
- Easy to understand and debug
- Efficient time complexity
Disadvantages:
- Requires two passes
- Slightly more complex than single pass
Solution 2: Single Pass with Array
Time Complexity: O(n) - Single pass through the strings
Space Complexity: O(1) - Fixed size arrays
Advantages:
- Most efficient approach
- Single pass through strings
- Simple implementation
- Optimal space usage
Disadvantages:
- Slightly harder to understand
- Requires careful frequency calculation
Solution 3: Brute Force
Time Complexity: O(n²) - For each guess digit, scan secret
Space Complexity: O(1) - Constant extra space
Advantages:
- Simple and straightforward
- Easy to implement
- No complex data structures
Disadvantages:
- Less efficient
- Higher time complexity
- Not suitable for large inputs