Like Tree4Likes

how to solve this problem

This is a discussion on how to solve this problem within the C Programming forums, part of the General Programming Boards category; You are given a set of digits, your task is to find the maximum integer that you can make from ...

  1. #1
    Registered User
    Join Date
    Aug 2012
    Posts
    23

    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

  2. #2
    msh
    msh is offline
    Novice
    Join Date
    Jul 2009
    Posts
    568
    It might involve writting some code... I dunno...
    Disclaimer: This post shows my ignorance at the time of its making. I claim ownership of but not responsibility for all errors in it. Reference at your own peril.

  3. #3
    Registered User
    Join Date
    Aug 2012
    Posts
    41
    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

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,758
    If there are multiple answers what should we print?
    Read the problem, there is only one "maximum" ...

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  6. #6
    Registered User
    Join Date
    Aug 2012
    Posts
    23
    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

  7. #7
    Registered User
    Join Date
    Aug 2012
    Posts
    41
    Quote Originally Posted by lovelycse View Post
    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'.

  8. #8
    Registered User
    Join Date
    Aug 2012
    Posts
    23
    thanx ...it works...ur logic ...sum and add...
    Quote Originally Posted by sana.iitkgp View Post
    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'.

  9. #9
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    The problem will still be which digit(s) to remove such that sum is three and the overall represented integer is maximized.

  10. #10
    Registered User
    Join Date
    Aug 2012
    Posts
    23
    @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 :-)

  11. #11
    Registered User
    Join Date
    Aug 2012
    Posts
    23
    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

  12. #12
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,758
    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.

  13. #13
    Registered User
    Join Date
    Aug 2012
    Posts
    41
    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'.

  14. #14
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,758
    The sum will always be peanuts compared to the product.

  15. #15
    Registered User
    Join Date
    Aug 2012
    Posts
    23
    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);
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to solve this problem?
    By lijr07 in forum C++ Programming
    Replies: 13
    Last Post: 07-30-2011, 01:53 PM
  2. Problem I Can't solve...
    By ferniture in forum C Programming
    Replies: 3
    Last Post: 07-15-2008, 03:51 AM
  3. how do i solve this problem?
    By manav in forum A Brief History of Cprogramming.com
    Replies: 31
    Last Post: 04-15-2008, 10:58 AM
  4. Would someone solve my problem?
    By Lonners in forum C Programming
    Replies: 9
    Last Post: 01-19-2008, 06:58 PM
  5. Plz solve my problem !
    By pankaj8096 in forum C Programming
    Replies: 12
    Last Post: 01-16-2003, 12:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21