C program to find minimum solution to reach a number N using only two opration.

Discussion in 'C Programming' started by Aditi, Oct 12, 2017.

  1. Aditi

    Aditi

    Joined:
    Oct 12, 2017
    Messages:
    3
    Likes Received:
    0
    hello, What is the code for this C program or logic?

    Given a number N the task is to find an optimal solution to reach N
    using two operations only. First option is operation 0: Double the
    number and second option is operation is 1: Add one to the number.
    Your task is to reach the number with minimum as many number of
    operations as possible.
    Input : N = 8
    Output : 4 Operations are required (two times operation 1 + two
    times operation 0)
    Start with 0 (always):
    Operation 1: 0 + 1 = 1
    Operation 1: 1 + 1 = 2
    Operation 0: 2 * 2 = 4
    Operation 0: 4 * 2 = 8

    thank you.
     
    Aditi, Oct 12, 2017
    #1
    1. Advertisements

  2. Aditi

    Cor

    Joined:
    Oct 13, 2017
    Messages:
    7
    Likes Received:
    0
    Cor, Oct 13, 2017
    #2
    1. Advertisements

  3. Aditi

    Aditi

    Joined:
    Oct 12, 2017
    Messages:
    3
    Likes Received:
    0

    Hi thank you for the very nice explanation :)
    How can I print the operation performed?? after getting the answer how can i print these steps?

    "" Operations are required (two times operation 1 + two
    times operation 0)
    Start with 0 (always):
    Operation 1: 0 + 1 = 1
    Operation 1: 1 + 1 = 2
    Operation 0: 2 * 2 = 4
    Operation 0: 4 * 2 = 8""

    For each number these steps(increment or double ) need to be printed along with the counter for no. of operation .

    for example if its 13 then all these line ashould get printed. How can this be done?

    " 6 Operations are required (four times operation 1 + two
    times operation 0)
    Start with 0 (always):
    Operation 1: 0 + 1 = 1
    Operation 1: 1 + 1 = 2
    Operation 1: 2 +1 = 3
    Operation 0: 3* 2 = 6
    Operation 0: 6 * 2 = 12
    Operation 1: 12 + 1 = 13"

    please if you can help .TIA
     
    Aditi, Oct 14, 2017
    #3
  4. Aditi

    Cor

    Joined:
    Oct 13, 2017
    Messages:
    7
    Likes Received:
    0
    Hi Aditi,

    what have you tried until now?

    Regards,

    Cor
     
    Cor, Oct 16, 2017 at 8:19 AM
    #4
  5. Aditi

    Aditi

    Joined:
    Oct 12, 2017
    Messages:
    3
    Likes Received:
    0
    Hi
    tried with this logic

    #include<stdio.h>
    int main()
    {
    int a[20],j,i,n,counter=0,b=0;
    printf("Enter the number of n");
    scanf("%d",&n);

    while(n>0)
    {
    if(n%2==0)
    {
    n=n/2;
    a[i++]=0;
    counter++;
    }
    else
    {
    n=n-1;
    a[i++]=1;
    counter++;

    }
    }

    while(i>=0)
    {
    if(a==1)
    {
    printf("Opration 1 : %d + 1 = %d",b,b+1);
    b=b+1;
    }
    else
    {
    printf("Opration 2 : %d * 2 = %d",b,b*2);
    b=b*2;
    }
    }
    printf("Minimum number of steps required to get the given target array is");
    printf("%d",counter);
    return 0;
    }
     
    Aditi, Oct 17, 2017 at 4:35 PM
    #5
  6. Aditi

    Cor

    Joined:
    Oct 13, 2017
    Messages:
    7
    Likes Received:
    0
    Hi Aditi,

    you're on the right track :)
    When converting decimal to binary, you should always do n = n/2 in the while Loop. (initialize i with 0 before the Loop; if your Compiler does not set i to 0, you will get a Segmentation fault ...)
    Second while Loop: if (a==1) is wrong; a is an Array, so this Statement will always be false and your program will only Output Opration2: ... When using a do something like if (a[ i ]==1)
    Be carefull though; when entering the while Loop, i is pointing somewhere beyound the Array, so decrement i by one before entering the while Loop; then you could use a.

    Regards,

    Cor


    #include <stdio.h>
    #include <stdlib.h>

    int main(int argc, char **argv)
    {
    int a[20],j,i,n,counter=0,b=0;
    int add_operation = 0, mul_operation = 0;

    n = atoi(argv[1]);

    while(n>0)
    {
    if(n%2==0)
    {
    a[counter++]=0;
    printf("lsb equals zero, so no addition later on\n");
    }
    else
    {
    a[counter++]=1;
    printf("lsb equals one, so add one later\n");
    add_operation++;
    }
    printf("always divide by 2, so always multiply later\n");
    mul_operation++;
    n=n/2;
    }

    printf("\n");

    for (int j=counter-1;j>=0;j--)
    {
    if (a[j]) printf("plus 1\n");
    if (j!=0) printf("multiply by 2\n");
    }

    printf("#additions: %d, number of multiplications: %d, total operations: %d\n\n",add_operation,mul_operation,add_operation+mul_operation);

    printf("binary representation of %d: ",atoi(argv[1]));
    for (int j=counter-1;j>=0;j--) printf("%d",a[j]);
    printf("\n");

    }
     
    Cor, Oct 18, 2017 at 7:26 AM
    #6
    1. Advertisements

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Similar Threads
  1. HVPQ
    Replies:
    5
    Views:
    1,218
  2. John
    Replies:
    1
    Views:
    5,967
    Ingo R. Homann
    Sep 26, 2006
  3. pradt@yahoo.com

    How to find minimum of two numbers.

    pradt@yahoo.com, Dec 10, 2004, in forum: C Programming
    Replies:
    29
    Views:
    4,169
    Frank J. Lhota
    Dec 13, 2004
  4. Magnus
    Replies:
    2
    Views:
    637
    bruce barker
    Jul 11, 2007
  5. Alan Isaac

    find minimum associated values

    Alan Isaac, Jan 25, 2008, in forum: Python
    Replies:
    8
    Views:
    486
    Alan Isaac
    Jan 25, 2008
  6. Peng Yu
    Replies:
    8
    Views:
    453
    Simon Forman
    Sep 21, 2009
  7. OrganicFreeStyle

    Set minimum for random number generator

    OrganicFreeStyle, Jun 11, 2006, in forum: Ruby
    Replies:
    3
    Views:
    185
    Serendipity
    Jun 27, 2006
  8. Cheryl M.

    Creating a Reach Program

    Cheryl M., Mar 27, 2011, in forum: Ruby
    Replies:
    1
    Views:
    165
    Robert Klemme
    Mar 28, 2011
Loading...