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.
