I am getting wrong output

Question

0.00/5 (No votes)

See more:

Question:

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

For example:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

ANSWER to BE DONE FOR THE INPUT:

*g= 
[262,437,433,102,438,346,131,160,281,34,219,373,466,275,51,118,209,32,108,57,385,514,439,73,271,442,366,515,284,425,491,466,322,34,484,231,450,355,106,279,496,312,96,461,446,422,143,98,444,461,142,234,416,45,271,344,446,364,216,16,431,370,120,463,377,106,113,406,406,481,304,41,2,174,81,220,158,104,119,95,479,323,145,205,218,482,345,324,253,368,214,379,343,375,134,145,268,56,206]

*s=
[149,79,388,251,417,82,233,377,95,309,418,400,501,349,348,400,461,495,104,330,155,483,334,436,512,232,511,40,343,334,307,56,164,276,399,337,59,440,3,458,417,291,354,419,516,4,370,106,469,254,274,163,345,513,130,292,330,198,142,95,18,295,126,131,339,171,347,199,244,428,383,43,315,353,91,289,466,178,425,112,420,85,159,360,241,300,295,285,310,76,69,297,155,416,333,416,226,262,63,445,77,151,368,406,171,13,198,30,446,142,329,245,505,238,352,113,485,296,337,507,91,437,366,511,414,46,78,399,283,106,202,494,380,479,522,479,438,21,130,293,422,440,71,321,446,358,39,447,427,6,33,429,324,76,396,444,519,159,45,403,243,251,373,251,23,140,7,356,194,499,276,251,311,10,147,30,276,430,151,519,36,354,162,451,524,312,447,77,170,428,23,283,249,466,39,58,424,68,481,2,173,179,382,334,430,84,151,293,95,522,358,505,63,524,143,119,325,401,6,361,284,418,169,256,221,330,23,72,185,376,515,84,319,27,66,497]


EXPECTED OUTPUT:  99

OUTPUT I AM GETTING: 98

I WAS UNABLE TO DEBUG FOR THE LARGE INPUT

What I have tried:

C++

int findContentChildren(int* g, int gSize, int* s, int sSize){
    if(sSize<1)
    {
        return 0;
    }
    if(gSize<1)
    {
        return sSize;
    }
    int max1=g[0];
    int max2=s[0];
    int max=0;
    for(int i=0;i<gSize;i++)
    {
        if(g[i]==0)
        {
            max++;
        }
    }
    for(int i=1;i<gSize;i++)
    {
        if(max1<g[i])
        {
            max1=g[i];
        }
    }
    for(int i=1;i<sSize;i++)
    {
        if(max2<s[i])
        {
            max2=s[i];
        }
    }
    int hash1[max1+1];
    int hash2[max2+1];
    for(int i=0;i<max1+1;i++)
    {
        hash1[i]=0;
    }
    for(int i=0;i<max2+1;i++)
    {
        hash2[i]=0;
    }
    for(int i=0;i<gSize;i++)
    {
        hash1[g[i]]++;
    }
     for(int i=0;i<sSize;i++)
    {
        hash2[s[i]]++;
    }
    for(int i=1;i<max2+1;i++)
    {
        if(i==0)
        {
            i++;
        }
        if(hash2[i]>0)
        {
            if(i<max1+1)
            {
                if(hash1[i]>0)
                {
                    max++;
                    hash1[i]--;
                     hash2[i]--;
                    i--;
                }
                else
                    for(int j=1;j<i;j++)
                    {
                        if(hash1[j]>0)
                        {
                            max++;
                            hash1[j]--;
                            hash2[i]--;
                            i--;
                            break;
                        }
                    }
            }
        }
    }
    return max;
}

Posted 16-Jul-21 20:16pm

_-_-_-me

Updated 17-Jul-21 3:13am

Add a Solution

Comments

Richard MacCutchan 17-Jul-21 5:21am

OK, rereading the question I count the number of cookies and get: 99.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2021-07-16T20:45:00

Quote:
I WAS UNABLE TO DEBUG FOR THE LARGE INPUT

And as you have been told before, that's the way you do it.
Grab the debugger, start adding breakpoints, and work out what you expect to happen before you execute a chunk of code. Then compare that to what does happen. If it matches, move on. If it doesn't ... start looking more closely at the offending chunk. More breakpoints, single stepping - you know what you have to do!

That's exactly what we would have to do ... and it's your homework, not ours! :laugh:

Richard MacCutchan · Accepted Answer · 2021-07-17T00:24:00

I solved this in a few lines of Python, but the principle is the same for any language. I started by sorting both lists and then for each child in g find the closest match in s. When a match is found, remove that entry from s (set it to zero) as that cookie has been taken, and add 1 to the count. Repeat for all entries in g.

I tried this with g sorted in ascending and descending order and the count was the same, although the actual cookie allocation was slightly different. By printing the child and cookie id each time a match was made, it was easy to see whether the code was working or not.

Patrice T · Accepted Answer · 2021-07-17T03:13:00

C++

int findContentChildren(int* g, int gSize, int* s, int sSize){
    if(sSize<1)
    {
        return 0;
    }
    if(gSize<1)
    {
        return sSize; // what make you think number of cookies is the answer when there is no child ?
    }

Quote:
I WAS UNABLE TO DEBUG FOR THE LARGE INPUT

The debugger is not the only technique for debugging.
You can some code at key points to check that everything goes well til that point.

C++

int hash1[max1+1];
int hash2[max2+1];
for(int i=0;i<max1+1;i++)
{
    hash1[i]=0;
}
for(int i=0;i<max2+1;i++)
{
    hash2[i]=0;
}
for(int i=0;i<gSize;i++)
{
    hash1[g[i]]++;
}
 for(int i=0;i<sSize;i++)
{
    hash2[s[i]]++;
}
// at this point, add code to check the hash1 and hash2 contain the correct number of children and cookies
// it is a leak detection
for(int i=1;i<max2+1;i++)

Print remaining hash1 and hash2 at the end of your routine, it may highlight a problem.

Advice: add high level comments, it help others to understand your code.

C++

// calculating maximum size of cookies

try to solve this input by hand, do you need to use hash to get the solution?
g = [1,2,3000000], s = [1,1000000]
g = [1,2,3], s = [1000000,1]
How you solved the problem by hand should be your algorithm.

I am getting wrong output

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0