Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
673 views
in Online Assessments by Expert (111,530 points) | 673 views

2 Answers

0 like 0 dislike
Best answer

image
image
image

 

I had done the brute Force Approach. I know that, it gives TLE. Can anyone suggest how can we solve the problem in optmized way.

 

Here is my bruteForce solution:

 

int countBoxes(string digits, vector<string> passwords)
{
    int openBoxes = 0;
    bool flag = true;
    vector<int> digitsFreq(10), passwordFreq(10);
    for (auto &digit : digits)
        digitsFreq[digit - '0']++;
    for (auto &password : passwords)
    {
        for (auto &ch : password)
            passwordFreq[ch - '0']++;
        flag = true;
        for (int i = 0; i <= 9; i++)
        {
            if (digitsFreq[i] < passwordFreq[i])
                flag = false;
            passwordFreq[i] = 0;
        }
        if (flag)
            openBoxes++;
    }
    return openBoxes;
}
by Expert (111,530 points)
0 like 0 dislike
I think your approach is fine but you can optimize it by a quite a bit.

Use array, not vector. Vector is known to be slow.
Check the validity while you are going through each password, so we can stop early.

Maybe adding bit of filtering, eg. password.size() <= digits.size() etc could help filter out unnecessary computations
checking if passwordFreq[ch-'0'] > digitsFreq[ch-'0'] at every update, can also prevent further un required computations

Yes but it'll improve overall complexity
All the passwords whose length is more than digits can't be part of answer
At any point while processing, if frequency exceeds frequency in digits, its not an answers
Similarly other cases might be there, which will filter out unrequired processing for overall 100+ passwords

Your time complexity is n*length of passwords (102 * 10^5)
Filtering might leave only lets say 70 * 10^5 (and those 10^5 words might also get filter before processing the entire length, so maybe average processed length might fall below 10^5)
by Expert (111,530 points)