# LC 299. Bulls and Cows

### [Problem link](https://leetcode.com/problems/bulls-and-cows/)

###### tags: `leedcode` `medium` `c++`

You are playing the **<a href="https://en.wikipedia.org/wiki/Bulls_and_Cows" target="_blank">Bulls and Cows</a>** 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. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number <code>secret</code> and your friend's guess <code>guess</code>, return the hint for your friend's guess.

The hint should be formatted as <code>"xAyB"</code>, where <code>x</code> is the number of bulls and <code>y</code> is the number of cows. Note that both <code>secret</code> and <code>guess</code> 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:**

- <code>1 <= secret.length, guess.length <= 1000</code>
- <code>secret.length == guess.length</code>
- <code>secret</code> and <code>guess</code> consist of digits only.

## Solution 1
#### C++

class Solution {
public:
    string getHint(string secret, string guess) {
        int n = secret.size();
        int a = 0;
        int b = 0;
        int cnt0[10];
        int cnt1[10];

        for (int i = 0; i < n; i++) {
            if (secret[i] == guess[i]) {
                a++;
            } else {
                cnt0[secret[i] - '0']++;
                cnt1[guess[i] - '0']++;
            }
        }
        for (int i = 0; i < 10; i++) {
            b += min(cnt0[i], cnt1[i]);
        }
        return to_string(a) + "A" + to_string(b) + "B";
    }
};

>### Complexity
>n = secret.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
x