Dare2Solve
The problem involves a game where you are given two strings: secret
and guess
, both of the same length. You need to provide a hint that includes:
The output should be a string formatted as "xAyB"
, where x
is the number of bulls and y
is the number of cows.
To solve this problem, we need to distinguish between two scenarios:
guess
exactly matches the corresponding digit in secret
(a bull).guess
is in secret
but in the wrong position (a cow).By counting bulls first and then handling cows based on the frequency of unmatched digits, we can efficiently compute the desired hint.
Initialize counters: Start with bulls = 0
, cows = 0
, and an array raj
of size 10 to keep track of the frequency of digits that have been encountered but not matched as bulls.
Iterate through the strings: For each character in the strings:
secret
and guess
match, increment the bulls counter.raj
array:
secret
was previously encountered in guess
, it means we have found a cow, so increment the cows counter.guess
was previously encountered in secret
, increment the cows counter.raj
array to reflect the current unmatched digits.Return the result: Format the result as "xAyB"
where x
is the number of bulls and y
is the number of cows.
O(n)
, where n
is the length of the strings secret
and guess
. We iterate through the strings once, making the solution linear in time.
O(1)
. The raj
array is of fixed size (10), and no additional space is used that scales with the input size.
class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0;
int cows = 0;
vector<int> raj(10, 0);
for (int i = 0; i < secret.length(); i++) {
int sec = secret[i] - '0';
int gu = guess[i] - '0';
if (sec == gu) {
bulls++;
continue;
}
if (raj[sec] < 0) {
cows++;
}
if (raj[gu] > 0) {
cows++;
}
raj[sec]++;
raj[gu]--;
}
return to_string(bulls) + "A" + to_string(cows) + "B";
}
};
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls = 0
cows = 0
raj = [0] * 10
for i in range(len(secret)):
sec = int(secret[i])
gu = int(guess[i])
if sec == gu:
bulls += 1
continue
if raj[sec] < 0:
cows += 1
if raj[gu] > 0:
cows += 1
raj[sec] += 1
raj[gu] -= 1
return f"{bulls}A{cows}B"
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0;
int cows = 0;
int[] raj = new int[10];
for (int i = 0; i < secret.length(); i++) {
int sec = Character.getNumericValue(secret.charAt(i));
int gu = Character.getNumericValue(guess.charAt(i));
if (sec == gu) {
bulls++;
continue;
}
if (raj[sec] < 0) {
cows++;
}
if (raj[gu] > 0) {
cows++;
}
raj[sec]++;
raj[gu]--;
}
return bulls + "A" + cows + "B";
}
}
/**
* @param {string} sec
* @param {string} guess
* @return {string}
*/
var getHint = function (sec, guess) {
let bulls = 0;
let cows = 0;
let raj = Array(10).fill(0);
for (let i = 0; i < sec.length; i++) {
let gu = parseInt(guess[i]);
let secret = parseInt(sec[i]);
if (secret === gu) {
bulls++;
continue;
}
if (raj[secret] < 0) {
cows++;
}
if (raj[gu] > 0) {
cows++;
}
raj[secret]++;
raj[gu]--;
}
return (`${bulls}A${cows}B`);
};