Click here to Skip to main content
15,035,723 members
Please Sign up or sign in to vote.
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
Updated 17-Jul-21 3:13am
Comments
Richard MacCutchan 17-Jul-21 5:21am
   
OK, rereading the question I count the number of cookies and get: 99.

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:
   
Comments
_-_-_-me 17-Jul-21 4:07am
   
Okay , thank you !!!
But the input is very long...
Its very hard...
OriginalGriff 17-Jul-21 4:30am
   
Yep. But that's the nature of the game.
One thing to try is cutting down the input - get it to a smaller size that still shows the problem and it can be easy to find out why.
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.
   
Comments
_-_-_-me 17-Jul-21 23:28pm
   
Okay, thank you !
I will first sort g and find out ...
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.
   
Comments
_-_-_-me 17-Jul-21 23:30pm
   
Thank you !
These two sentences helped a lot :
1) try to solve this input by hand, do you need to use hash to get the solution?
2) How you solved the problem by hand should be your algorithm.
_-_-_-me 18-Jul-21 0:39am
   
I understood how to debug in an efficient way.
Thank you!
Patrice T 18-Jul-21 0:53am
   
Nice to have been helpful.

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




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900