CODEWITHSUNDEEP
javaalgorithm
user697911
user697911

Reputation: 10551

Explanation of bulls and cows algorithm in leetcode

The algorithm is here: https://discuss.leetcode.com/topic/28463/one-pass-java-solution.

public static String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        int[] numbers = new int[10];
        for (int i = 0; i<secret.length(); i++) {
            int s = Character.getNumericValue(secret.charAt(i));
            int g = Character.getNumericValue(guess.charAt(i));
            if (s == g) bulls++;
            else {
                if (numbers[s] < 0){
                    cows++;
                }
                if (numbers[g] > 0){
                    cows++;
                }
                numbers[s] ++;
                numbers[g] --;
            }
        }
        return bulls + "A" + cows + "B";
    }

But how to understand this part: 

numbers[s] ++;
numbers[g] --;

Why does it use negative number to count occurrences in guess and positive number to count in secret.

Upvotes: 2

Views: 1302

Answers (1)

user3386109
user3386109

Reputation: 34839

The numbers array keeps track of the unmatched numbers seen in the two arrays. Initially each entry in the numbers array is 0, indicating that number has not been seen in either array. A positive entry means that the number was seen in the secret array more times than in the guess array. A negative entry means the number was seen in the guess array more times than in the secret array.

So when the algorithm sees a number in the secret array, it increases the corresponding entry in the numbers array. If that entry happened to be negative before the increment, it means that the number was already seen in the guess array, so the cows count is increased.

Likewise when the algorithm sees a number in the guess array, it decreases the corresponding entry in the numbers array. If that entry happened to be positive before the decrement, it means that the number was already seen in the secret array, so the cows count is increased.

Upvotes: 1

Related Questions