Thread: how to solve this problem

You are given a set of digits, your task is to find the maximum integer that you can make from these digits. The made number must be divisible by 2, 3, 5 without a residue. It is permitted to use not all digits from the set, it is forbidden to use leading zeroes.
Each digit is allowed to occur in the number the same number of times it occurs in the set.


Input
A single line contains a single integer n (1 ≤ n ≤ 1000) — the number of digits in the set.
The second line contains n digits, the digits are separated by a single space.


Output
On a single line print the answer to the problem. If such number does not exist, then you should print -1.


Sample test case:
Input
11
3 4 5 4 5 3 5 3 4 4 0

If there are multiple answers what should we print?

You can try this way.
If number of digits are lessthan 2 print -1 (as it should be divisible by 30 without any residue)
If none of the digits is '0' print -1
If the sum of digits is not divisible by '3' print -1
If it passes all the above conditions then print all the digits in any order keeping one '0' at the end. This is your answer

If there are multiple answers what should we print?

Read the problem, there is only one "maximum" ...

Using a paper and pencil (maybe a calculator), but not a computer, how would you solve this?

Repeat that problem solving exercise a few times, and you will see the pattern of logic - the algorithm if you will - of how you might solve it with the computer, using C. Break down the algorithm into smaller and smaller steps, until you can see how blocks of code could be substituted for the actions you were taking. That's your backbone of logic for the program.

With all your problems, it's VERY important that you make an initial effort, and post that. That we we can see what you're trying, and hopefully, you'll tell us in your post, what part of the problem has you stumped.

Posting your problem alone, is a start - but not enough for us to see what you have tried already, etc. Without that display of your work, we can't work efficiently. Try and be specific with your explanation of the problem you're having. The more specific you are, the more helpful we can be, because we understand just what you're doing, and what the problem is.

Output
5554443330
approach-> i sort the given integer for example if 11 integers are given like
33453545440
then first i will apply the sorting that will give
55544443330
next i will divide it by 30 boz 2*3*5=30
if the remainder is 0 then its the no that we r looking for...
but if fails then i will deduct the smallest no from set ...here smallest is 0 so resulting string of digit will 5554444333/30
further steps will be lyk this
if remainder is 0 then stop
otherwise reduce the next smallest digit from the set
here going this way
we found 5554443330

but the prob is... no of input digit can be upto 1000
then how its possible to divide 1000 string of digit by 30
as no data type can have the such large range...

kindly help
thank you

Originally Posted by lovelycse

but the prob is... no of input digit can be upto 1000
then how its possible to divide 1000 string of digit by 30
as no data type can have the such large range...

Instead of dividing with 30, add all digits and divide with '3'. If the sum of digits is divisible by '3' number is divisible by '3', so one of your digit is '0' and sum of digits is divisible by '3' your number is ready, otherwise remove one digit suchthat sum of digits is divisible by '3'.

thanx ...it works...ur logic ...sum and add...

Originally Posted by sana.iitkgp

Instead of dividing with 30, add all digits and divide with '3'. If the sum of digits is divisible by '3' number is divisible by '3', so one of your digit is '0' and sum of digits is divisible by '3' your number is ready, otherwise remove one digit suchthat sum of digits is divisible by '3'.

The problem will still be which digit(s) to remove such that sum is three and the overall represented integer is maximized.

@nonoob
we'll first sort the input integer then only sum up and if the resultant sum is nt divisible by 3 only then we have toremove one smallest integer and as i told its sorted so finding the smallest no is nt a big task...then next smallest ..continue in this fashion............will get u the haighest number divisible by 2 3 and 5...i hope it is clear now :-)

hey if i remove one by one digits then its nt applicable to the number lyk 5320 ...here we will have to remove the 5 and 2 both so how to proceed....for removal of two digits at a same tym

3 +4 +5 +4 +5 +3 +5 +3 +4 +4 is 40, not a multiple of 30, so addition doesn't work. When I initially thought of the problem, I thought you would multiply the digits together, as long as they were multiples of 2, 3 or 5. That would net you pretty big answers. But if the answer is supposed to be a permutation of digits, then I would just work at it from that angle. Find the permutations and test them. It kind of sucks that the test case did not give an answer. I mean, it's possibly 864000 or something bigger.

Remainder of sum of digits divided by 3 is either '0','1','2'. In the above case it is '1'. So if any of your digits is '1' or '4' or '7' you can directly remove them, otherwise you need to remove two digits from set of '2','5','8' so that the sum is divisible by '3'.

The sum will always be peanuts compared to the product.

what is the prob in this

Code:

#include<stdio.h>
int main()
{
    int a[1000],b[1000],c[1000],new1[1000];
    int temp=0,n,q,m,i,j,s,sum=0,flag=0,k,r,flag1=0,sum1=0,count=0,flag2=0;
    //printf("enter the intergr");
    scanf("%d",&n);
    //printf("\n");
    s=n;
    for(i=0;i<n;i++)
    {
        scanf("%d",&c[i]);
    }
    for(i=0;i<=n-2;i++)
    {
        for(j=i+1;j<=n-1;j++)
        {
            if ( c[i] > c[j] )
            {
                temp = c[i] ;
                c[i] = c[j] ;
                c[j] = temp ;
            }
        }
    }
i=0;
q=0;
for(i=n-1;i>=0;i--)
{
a[q]=c[i];
//printf("a[q]%d\n",a[q]);
q++;
}
i=0;
j=0;
if(a[n-1]==0)
{
        i=0;
        for(i=0;i<n;i++)
        {
            sum=sum+a[i];
        }
        printf("sum\n%d",sum);
        r=sum%3;
        //printf("r\n%d",r);
        if(r==0)
        {
            flag=1;
            m=i;
            //printf("YES\n");
        }
        r=0;
        else
        {
        for(j=n-1;j>=0;j--)
        {
        r=a[j]%3;
        if((r==1)||(r==2))
        {
        sum=sum-a[j];
        a[j]=0;
        
        k=sum%3;
        if(k==0)
        break;    
        }    
        }
        }
        i=0;
        for(i=0;i<n;i++)
        {
        printf("%d",a[i]);
        }        
        
}    
else
printf("-1");        
return(0);
}