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

[Aditi]

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.

 

[Cor]

Hi Aditi,

try to explain your teacher why the following works

int opcnt = -1;
while (n>0)
{
opcnt += (n&1)+1;
n >>= 1;
}
printf("%d\n",opcnt);

Regards,

Cor

P.S: https://en.wikipedia.org/wiki/Binary_number#Decimal

 

[Aditi]

Hi Aditi,

try to explain your teacher why the following works

int opcnt = -1;
while (n>0)
{
opcnt += (n&1)+1;
n >>= 1;
}
printf("%d\n",opcnt);

Regards,

Cor

P.S: https://en.wikipedia.org/wiki/Binary_number#Decimal

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

 

[Cor]

Hi Aditi,

what have you tried until now?

Regards,

Cor

 

[Aditi]

Hi Aditi,

what have you tried until now?

Regards,

Cor

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;
}

 

[Cor]

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");

}

 

[Aditi]

Thank you so much Cor