Brute force solution for DCE05 (Odd) gives WA

#include <stdio.h>
#include <math.h>
int main (void)
{
int x, y, z;
scanf ("%i", &x);
for (x; x > 0; --x)
{
scanf ("%i", &y);
if ( y == 0 )
printf (“1\n”);
else if (y == 1)
printf (“1\n”);
else if (y == 2 || y == 3)
printf (“2\n”);
else if (y < 4 && y >= 2 )
printf (“2\n”);
else if (y < 8 && y >= 4)
printf (“4\n”);
else if (y < 16 && y >= 8)
printf (“8\n”);
else if (y < 32 && y >= 16)
printf (“16\n”);
else if (y < 64 && y >= 32)
printf (“32\n”);
else if (y < 128 && y >= 64)
printf (“64\n”);
else if (y < 256 && y >= 128)
printf (“128\n”);
else if (y < 512 && y >= 256)
printf (“256\n”);
else if (y < 1024 && y >= 512)
printf (“512\n”);
else if (y < 2048 && y >= 1024)
printf (“1024\n”);
else if (y < 4096 && y >= 2048)
printf (“2048\n”);
else if (y < 8192 && y >= 4096)
printf (“4096\n”);
else if (y < 16384 && y >= 8192)
printf (“8192\n”);
else if (y < 32768 && y >= 16384)
printf (“16384\n”);
else if (y < 65536 && y >= 32768)
printf (“32768\n”);
else if (y < 131072 && y >= 65536)
printf (“65536\n”);
else if (y < 262144 && y >= 131072)
printf (“131072\n”);
else if (y < 524288 && y >= 262144)
printf (“262144\n”);
else if (y < 1048576 && y >= 524288)
printf (“524288\n”);
else if (y < 2097152 && y >= 1048576)
printf (“1048576\n”);
else if (y < 4194304 && y >= 2097152)
printf (“2097152\n”);
else if (y < 8388608 && y >= 4194304)
printf (“4194304\n”);
else if (y < 16777216 && y >= 8388608)
printf (“8388608\n”);
else if (y < 33554432 && y >= 16777216)
printf (“16777216\n”);
else if (y < 67108864 && y >= 33554432)
printf (“33554432\n”);
else if (y < 134217728 && y >= 67108864)
printf (“67108864\n”);
else if (y < 268435456 && y >= 134217728)
printf (“134217728\n”);
else if (y < 536870912 && y >= 268435456)
printf (“268435456\n”);
else if (y < 1073741824 && y >= 536870912)
printf (“536870912\n”);
}

    return 0;
}

Why is it giving wrong answer? I have compared the output of this program with another accepted solution. Both were identical. I am new to programming and hence I do not know about any algorithms. This is the best I could come up with.

hi @gautam94 well you’ve cracked the question only:

As you saw the constraint is n<=10^9 which doesn’t fit in the range of a normal int!

So, first of all you need to declare all the variables long instead of int.

Now, obviously if you change the datatype you have to change the scanf parameters as well right?
I dont know why you have used %i. Generally for int we use %d and for long int we use %ld.

so From your code replace following lines:

 <pre>
    int x, y, z;
    scanf ("%i", &x);
    for (x; x > 0; --x)
    {
        scanf ("%i", &y);
    .
    .
    .

with following lines:

<pre>
    long int x, y, z;
    scanf ("%ld", &x);
    for (x; x > 0; --x)
    {
        scanf ("%ld", &y);
    .
    .
    .
    

this should get you accepted.(Notice the changes)

Hope this helps :slight_smile:

2 Likes

Also, @gautam94 my solution was very similar to yours, the same logic which yields you so many if-else statements can be done simply in a while loop. After you get this one submitted, check this.
If you find it difficult to understand just take a pen and paper and a sample case and follow the loops you’ll understand that its the same thing as you’ve done!
Hope this helps as well :slight_smile:

1 Like

@sunny_patel…int can very well store a number upto 10^9…!!!.

see this link…LINK!!!

2 Likes

@kunal361 yes i know. But i said it according to the range that we are aware of. I dont know why this happens always. See this there is a table that shows range of various datatypes. But it also says its machine dependent. So i am not sure which one to trust! but to be on safer side i suggested long. Also his solution failed so i thot that might be the problem! :slight_smile: @gautam94 Agreeing to @kunal361 , your solution should have been accepted. Try changing %i to %d and see if it passes. :slight_smile:

sorry @gautam94 as @kunal361 pointed out, int does work in your solution so the problem was only about %i and %d. However using long won’t reduce your bank balance anyway :smiley: :stuck_out_tongue: JK :slight_smile:

2 Likes

I am learning C from ‘Programming in C’ by Stephen Kochan. All the programs have been written with %i instead of %d and they compile with any error. (I use GCC 4.6.2) So I guess the error was not because of the format specifier. Anyways, I will still try that once.

I understood your solution. Thanks.

ok. i think it has to do something with GCC versions only! %i to %d without any other change gets AC, and so does the solution with long instead of int. So maybe %i isnt supported.

1 Like

Changing %i to %d worked! But I don’t understand why %i was giving wrong answer.

Thanks. But why %i does not work in this case?

here is the answer @gautam94

1 Like

Hello,

Taken from some forum:

“%d effectively calls strtol with a base of 10, so it assumes all numbers
it reads are decimal. %i effectively calls strtol with a base of 0, so it
adapts the base according to any prefix (0, 0x, or 0X) it sees. Thus 08
is an ill formed octal integer.”

This means that is the data is formatted such that some special numbers are encountered, like with 0s as prefix (it can happen), then using %d will ignore them, while using %i will convert them to Octal format…

The common practice is to use %d instead of %i :slight_smile:

Best regards,

Bruno

1 Like

Thanks for your help.

//