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:
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.
Example 1:
Input: secret = "1807", guess = "7810" Output: "1A3B" Explanation: Bulls are connected with a '|' and cows are underlined: "1807" | "7810"
Example 2:
Input: secret = "1123", guess = "0111" Output: "1A1B" Explanation: Bulls are connected with a '|' and cows are underlined: "1123" "1123" | or | "0111" "0111" Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.
Constraints:
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret and guess consist of digits only.The idea is to first determine the number of bulls by comparing characters at the same position in both the secret and the guess. In the first pass over the strings, count all bulls and track unmatched characters using two separate frequency arrays. In the second pass, use the frequency arrays to compute the number of cows by checking the minimum frequency of each character in unmatched parts.
In this C solution, two integer arrays secretCount and guessCount are used to count how many times each digit appears in the unmatched parts of secret and guess. After counting bulls and populating these arrays in the first loop, the second loop calculates cows by summing the minimum of matched counts in secretCount and guessCount.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1), where n is the length of the secret or guess.
Instead of performing two separate passes, this method uses a hashmap (or dictionary) to update the unmatched digits' count as it checks for bulls and non-bulls in a single iteration over the inputs. It utilizes incremental checking for cows during the mismatched segments.
This C function uses a single-pass approach with an array used as a hashmap to track digits. When encountering a mismatch, it checks and updates the hashmap to calculate cows immediately.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Counting Bulls and Cows with Two Passes | Time Complexity: O(n), Space Complexity: O(1), where n is the length of the secret or guess. |
| Single Pass Hashmap Tracking | Time Complexity: O(n), Space Complexity: O(1). |
bulls and cows | bulls and cows leetcode | leetcode 299 | string • Naresh Gupta • 14,913 views views
Watch 9 more video solutions →Practice Bulls and Cows with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor