*I made a mistake everywhere in if else ... mistake is in bold*
if(b[i]==3 && count==0)
{
gp3[r][0]=gp3[r][1]=gp3[r][2]=
b[i];
r++;
}
elseif*(b[i]==3 && count!=0)*
{
gp2[l][0]=gp2[l][1]=b[i];
l++;
gp2[l][0]=b[i];
gp2[l][1]=m[n];
l++;
n--;
}
On Sat, Jul 9, 2011 at 2:27 AM, Yogesh Yadav <[email protected]> wrote:
> let 10 digit phone number stored in array a[]
>
> take a array b[10] and initialise its elements with 0
>
> int gp2[][2]; // group with 2 elements will store here
> int gp3[][3]; // group with 3 elements will store here
> int l=0,r=0,count=0;
> int m[],n; //l,m,n is global
>
> for(i=0;i<10;i++)
> b[a[i]]++;
>
> for(i=0;i<10;i++)
> {
> if(b[i]==1)
> count++; //finding number of single elements
> for(j=0;j<10;j++)
> if(a[j]==i) //finds the single value in array a[]
> {
> m[n]=a[j]; //assign that single value in array m[]
> n++;
> }
> }
> for(i=0;i<10;i++)
> {
> if(b[i]==2)
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
>
>
> if(b[i]==3 && count==0)
> {
> gp3[r][0]=gp3[r][1]=gp3[r][2]=b[i];
> r++;
> }
> else
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=b[i];
> gp2[l][1]=m[n];
> l++;
> n--;
> }
> if(b[i]==5 && count==0)
> {
> gp3[r][0]=gp3[r][1]=gp3[r][2]=b[i];
> r++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> else
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=b[i];
> gp2[l][1]=m[n];
> l++;
> n--;
> }
> if(b[i]==7 && count==0)
> {
> gp3[r][0]=gp3[r][1]=gp3[r][2]=b[i];
> r++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> else
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=b[i];
> gp2[l][1]=m[n];
> l++;
> n--;
> }
> if(b[i]==9 && count==0)
> {
> gp3[r][0]=gp3[r][1]=gp3[r][2]=b[i];
> r++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> else
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=b[i];
> gp2[l][1]=m[n];
> l++;
> n--;
> }
>
> if(b[i]==4) // dnt
> decrease quality even if count is not zero for even numbers
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> if(b[i]==6)
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> if(b[i]==8)
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> if(b[i]==10)
> {
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> gp2[l][0]=gp2[l][1]=b[i];
> l++;
> }
> // now may be even now count!=0 so we have to make it zero because this
> means some elements are present which occurs 1 times
> if(count==2) // 1 cannot be possible
> {
> gp2[l][0]=m[n]; //make any group as they don't effect quality
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> }
> if(count==3)
> {
> gp3[r][0]=m[n];
> n--;
> gp3[r][1]=m[n];
> n--;
> gp3[r][2]=m[n];
> n--;
> r++;
> }
> if(count==4)
> {
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
>
> }
>
> if(count==5)
> {
> gp3[r][0]=m[n];
> n--;
> gp3[r][1]=m[n];
> n--;
> gp3[r][2]=m[n];
> n--;
> r++;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> }
> if(count==6)
> {
> gp3[r][0]=m[n];
> n--;
> gp3[r][1]=m[n];
> n--;
> gp3[r][2]=m[n];
> n--;
> r++;
> gp3[r][0]=m[n];
> n--;
> gp3[r][1]=m[n];
> n--;
> gp3[r][2]=m[n];
> n--;
> r++;
>
> }
>
> if(count==7)
> {
> gp3[r][0]=m[n];
> n--;
> gp3[r][1]=m[n];
> n--;
> gp3[r][2]=m[n];
> n--;
> r++;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
>
> }
>
> if(count==8)
> {
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
>
> }
>
>
> if(count==10) // 9 cannot be possible
> {
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
> gp2[l][0]=m[n];
> n--;
> gp2[l][1]=m[n];
> l++;
> n--;
>
> }
> }
>
> On Fri, Jul 8, 2011 at 3:44 AM, sunny agrawal <[email protected]>wrote:
>
>> Nopes solution is for only groups of size 2 and 3.
>> solution is like a general DP
>>
>> for string of length i to j
>> there can be only 4 possibilities
>>
>> substring of length 2 from start + remaining string
>> substring of length 3 from start + remaining string
>> string except last 2 + value of last 2
>> string except last 3 + value of last 3
>>
>> assign value that is max of all 4
>>
>>
>> but see what i got
>> an O(N) solution
>> http://ideone.com/KWIL2
>> it is giving answer same as in first O(N^2) so i hope it is correct
>> it is like coin denomination
>> easy to get :)
>>
>>
>> On Fri, Jul 8, 2011 at 3:29 AM, Piyush Sinha <[email protected]>wrote:
>>
>>> Can u explain ur algo too??
>>>
>>> On 7/8/11, Piyush Sinha <[email protected]> wrote:
>>> > @Sunny...nice solution but ur solution works if there can 1 to 3
>>> > groups of digits..but in the question its mentioned the group should
>>> > contain exactly 2 or 3 digits...
>>> >
>>> > but anyways nice solution...:)
>>> >
>>> > On 7/8/11, sunny agrawal <[email protected]> wrote:
>>> >> http://ideone.com/xv73J
>>> >>
>>> >>
>>> >> On Fri, Jul 8, 2011 at 2:16 AM, Piyush Sinha
>>> >> <[email protected]>wrote:
>>> >>
>>> >>> @Sunny...can u post a definite algo for it??
>>> >>>
>>> >>> On 7/8/11, Ravi Shukla <[email protected]> wrote:
>>> >>> > @sunny , yep it looks DP. more of MCM.
>>> >>> >
>>> >>> > solve for substrings of length 1,2,3.
>>> >>> > and then apply DP[i][j]=max score for a substring from i to j.
>>> >>> > =max(DP[i][k]+DP[k][j]) where k>i && k<j .
>>> >>> >
>>> >>> > The complexity this approach renders would be O(n^3).
>>> >>> > with O(n^2) space complexity.
>>> >>> >
>>> >>> > anyone anything better ?
>>> >>> >
>>> >>> > Thanks.
>>> >>> > Ravi Shukla
>>> >>> > CSE Final Year.
>>> >>> > BIT Mesra, Ranchi
>>> >>> >
>>> >>> > --
>>> >>> > You received this message because you are subscribed to the Google
>>> >>> > Groups
>>> >>> > "Algorithm Geeks" group.
>>> >>> > To post to this group, send email to [email protected].
>>> >>> > To unsubscribe from this group, send email to
>>> >>> > [email protected].
>>> >>> > For more options, visit this group at
>>> >>> > http://groups.google.com/group/algogeeks?hl=en.
>>> >>> >
>>> >>> >
>>> >>>
>>> >>>
>>> >>> --
>>> >>> *Piyush Sinha*
>>> >>> *IIIT, Allahabad*
>>> >>> *+91-8792136657*
>>> >>> *+91-7483122727*
>>> >>> *https://www.facebook.com/profile.php?id=100000655377926 *
>>> >>>
>>> >>> --
>>> >>> You received this message because you are subscribed to the Google
>>> >>> Groups
>>> >>> "Algorithm Geeks" group.
>>> >>> To post to this group, send email to [email protected].
>>> >>> To unsubscribe from this group, send email to
>>> >>> [email protected].
>>> >>> For more options, visit this group at
>>> >>> http://groups.google.com/group/algogeeks?hl=en.
>>> >>>
>>> >>>
>>> >>
>>> >>
>>> >> --
>>> >> Sunny Aggrawal
>>> >> B-Tech IV year,CSI
>>> >> Indian Institute Of Technology,Roorkee
>>> >>
>>> >> --
>>> >> You received this message because you are subscribed to the Google
>>> Groups
>>> >> "Algorithm Geeks" group.
>>> >> To post to this group, send email to [email protected].
>>> >> To unsubscribe from this group, send email to
>>> >> [email protected].
>>> >> For more options, visit this group at
>>> >> http://groups.google.com/group/algogeeks?hl=en.
>>> >>
>>> >>
>>> >
>>> >
>>> > --
>>> > *Piyush Sinha*
>>> > *IIIT, Allahabad*
>>> > *+91-8792136657*
>>> > *+91-7483122727*
>>> > *https://www.facebook.com/profile.php?id=100000655377926 *
>>> >
>>>
>>>
>>> --
>>> *Piyush Sinha*
>>> *IIIT, Allahabad*
>>> *+91-8792136657*
>>> *+91-7483122727*
>>> *https://www.facebook.com/profile.php?id=100000655377926 *
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
