# 299. Bulls and Cows

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FmXlKZiXbmZH5J01QBwrZ%2F%E5%9C%96%E7%89%87.png?alt=media\&token=fd635faf-a801-4890-9252-f72a545ca1fb)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FKFikExm1cZON0lb6XnRW%2F%E5%9C%96%E7%89%87.png?alt=media\&token=b6c4394c-22a7-40e0-b34d-9dfdb1f5f1d1)

time: O(n), n is min(secret'len, 10)

space:O(1)

```java
class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        int[] secretCount = new int[10];
        int[] guessCount = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                bulls++;
            } else {
                secretCount[secret.charAt(i) - '0']++; // record number count
                guessCount[guess.charAt(i) - '0']++;
            }
        }
        for (int i = 0; i < 10; i++) {
            cows += Math.min(secretCount[i], guessCount[i]);
        }
        return bulls + "A" + cows + "B";
    }
}

/*
bulls correct position. x is the number of bulls
cows right number in secret, but in wrong position , can rearrange to be bulls, y is the number of cows

secret(ans), guess, return hint, xAyB


compare two String, if match bulls++
else
 record in counting array, countS[i]++, countG[i]++
 final 
 for (entire countS[]) {
    cows += Math.min(countS[i], countG[i])
 }
 
 
 ex: 
 1123
  b
 0111
 
 bulls = 1
 others not matches, but has common 1'num in both counter  
 
 time: O(n), n is min(secret'len, 10)
 space: O(1)
*/
```



以這例子來看

1A => 因為 index 1的地方是一樣的

B => guess 的 11 的確在 secret 有, 但不同位置

所以就算 secret 有三個 1 (排除了A的部分）, 也只會對到 2個 B

所以這也就是為什麼取 cows += Math.min(countS\[i], countG\[i]) 就好（也就是交集）

所以也就是為什麼 in else case, 不 match 時, 紀錄每個數字的 count 就可以做 B 了(這些 count 一定是位置不對的 count, 只是還不知道交集有多少個

&#x20;

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FfOb7lnueBGsTeSoSyp4P%2F%E5%9C%96%E7%89%87.png?alt=media\&token=1e59bbdb-5554-4573-9025-14bfd989b06b)
