# [C++] 4ms Straight forward solution two pass O(N) time

• The idea is simple, if two char is match, add aCnt, otherwise, record it and process bCnt in second pass.

``````class Solution {
public:
// only contains digits
string getHint(string secret, string guess) {
int aCnt = 0;
int bCnt = 0;
vector<int> sVec(10, 0); // 0 ~ 9 for secret
vector<int> gVec(10, 0); // 0 ~ 9 for guess
if (secret.size() != guess.size() || secret.empty()) { return "0A0B"; }
for (int i = 0; i < secret.size(); ++i) {
char c1 = secret[i]; char c2 = guess[i];
if (c1 == c2) {
++aCnt;
} else {
++sVec[c1-'0'];
++gVec[c2-'0'];
}
}
// count b
for (int i = 0; i < sVec.size(); ++i) {
bCnt += min(sVec[i], gVec[i]);
}
}
};``````

• Java version:

``````public String getHint(String secret, String guess)
{
int len = secret.length();
int nCows = 0;
int nBull = 0;
int[] diffS = new int[10];
int[] diffG = new int[10];
for(int i=0; i<len; ++i)
{
if(guess.charAt(i) == secret.charAt(i)) ++nBull;
else
{
++diffS[secret.charAt(i) - '0'];
++diffG[guess.charAt(i) - '0'];
}
}

for(int i=0; i<10; ++i)
{
nCows += Math.min(diffS[i], diffG[i]);
}

return "" + nBull + "A" + nCows + "B";
}
``````

• Excuse me. Can you provide more explanation about your codes. For example, what is the function of
++sVec[c1-'0'];
++gVec[c2-'0'];
and bCnt += min(sVec[i], gVec[i]);
Thank you

• Nice solution!!! Very smart idea to count the cow. Count the number of unpaired digits, and the less one is the cow number. Thank you very much.

• `++sVec[c1-'0']; ++gVec[c2-'0'];` is used to count digits' (0~9) number which are not paired. `bCnt += min(sVec[i], gVec[i]);` for example, sVec[1] =2, gVec[1] =3, means there are 2 '1' in secret and 3 '1' in guess can not find paired one, then at least there are 2 '1' is in the wrong place.

• This post is deleted!

• You took advantage of “only digits”. With no use of hash map, your program is definitely fast.

• The same as i thought. However, a bit difference appears in the count of cows. My solution is:
class Solution {
public:
string getHint(string secret, string guess) {
int cntA = 0, cntB = 0;
int tab[10] = {0};
string strTmp;
for (int i = 0; i != guess.size(); ++i) {
if (guess[i] == secret[i])
++cntA;
else {
++tab[secret[i] - '0'];
strTmp.push_back(guess[i]);
}
}
for (const char & c : strTmp) {
int & nTmp = tab[c - '0'];
if (nTmp) {
--nTmp;
++cntB;
}
}
stringstream s;
s << cntA << "A" << cntB << "B";
return s.str();
}
};
This one also achieve a 4ms process time.

• Mine is similar to yours.

``````class Solution {
public:
string getHint(string secret, string guess) {
unordered_map<char,int> hashtab;
int bulls=0,cows=0,size=secret.size();
for(int i=0;i<size;i++){
if(secret[i]==guess[i]) bulls++;
else hashtab[secret[i]]++;
}
for(int i=0;i<size;i++){
if(secret[i]!=guess[i]&&hashtab[guess[i]]>0){
hashtab[guess[i]]--;
cows++;
}
}
}
};
``````

• ``````string getHint(string secret, string guess) {
int m[10] = {0}, len = secret.size();
int A = 0, B = 0;

for(int i=0; i<len; i++) {
m[secret[i]-'0']++;
if(secret[i] == guess[i]) A++;
}

for(int i=0; i<len; i++) {
if(m[guess[i]-'0'] > 0) B++;
m[guess[i]-'0']--;
}

}
``````

• Nice solution! It is easy and concise, In my solution, I use two unordered_map ,also solve the problem. But it is complex!

``````
class Solution {
public:
string getHint(string secret, string guess) {
int len = secret.length();
unordered_map<int, int> m;//key represents the number，value represents the times of the number appearing
unordered_map<int, int> mm;
int bull = 0, cow = 0;
string res = "";
for (int i = 0; i<len; i++)
{
if (secret[i] == guess[i])//cow number
bull++;
else
{
m[secret[i] - '0']++;
mm[guess[i] - '0']++;
}
}
for (int i = 0; i<len; i++)
{
if (m.find(guess[i] - '0') != m.end())//m has the number
{
if (mm[guess[i] - '0']>0&&m[guess[i] - '0']>0)
{
cow++;
mm[guess[i] - '0']--;
m[guess[i] - '0']--;
}
}
}
res = to_string(bull) + "A" + to_string(cow) + "B";
return res;
}
};
``````

• Really nice solution !
Using vectors for recording is really smart

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.