-1

I was solving the power sum problem (aka all possible ways problem in coding ninja).

Given two integers a and b. You need to find and return the count of possible ways in which we can represent the number a as the sum of unique integers raise to the power b.

Below is the code for that:

#include <iostream>
#include <cmath>
using namespace std;

int getAllWays(int b, int li, int rem)
{
    if (rem==0)
    {
        return 1;
    }
    if (li<=0)
    {
        return 0;
    }
    int remrt = pow(rem,(1.0/b));
    while(remrt>=li)
    {
        remrt--;
    }
    // Select case
    int v1 = getAllWays(b, remrt, rem-pow(remrt,b));
    // Reject case
    int v2 = getAllWays(b, remrt, rem);
    return v1+v2;
}

int getAllWays(int a, int b)
{
    // Write your code here
    int li = pow(a,(1.0/b));
    li++;
    return getAllWays(b, li, a);
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout <<getAllWays(a, b);
}

For input 100 2 I'm getting output 4 in my visual studio code whereas output 3 in online compilers such as Jdoodle and ideone.com. Correct output is 3.

What could be the reason? My terminal shows g++ version as below:

C:\Users\username>g++ --version
g++ (MinGW.org GCC-6.3.0-1) 6.3.0
Copyright (C) 2016 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

VS Code Screenshot: enter image description here

Ideone link: https://ideone.com/6nDaQI

CodeHackeRツ
  • 37
  • 5
  • 6
    Different output from different compilers typically depends on your code having *undefined behavior* somewhere. You need to [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your code. – Some programmer dude Mar 14 '23 at 16:23
  • https://meta.stackoverflow.com/questions/285551/why-not-upload-images-of-code-errors-when-asking-a-question – Marek R Mar 14 '23 at 16:23
  • 1
    What _should_ the answer be with input of `100 2`? I don't know what this problem is, so I don't know what the answer should be. – JohnFilleau Mar 14 '23 at 16:24
  • Sanitizers do not find anything: https://godbolt.org/z/hdG4Y7o59 :/ – Marek R Mar 14 '23 at 16:27
  • 2
    Probably problem is rounding issue. Size of double on MSVC and gcc are diffrent and as result precision is different. Now since you are do conversion from `double` to `int` and result may be close to integer value, you can be just below integer or not. See: https://stackoverflow.com/questions/588004/is-floating-point-math-broken – Marek R Mar 14 '23 at 16:30
  • How does one specify stdin in godbolt? – Thomas Weller Mar 14 '23 at 16:31
  • @ThomasWeller there is `stdin` button with a compiler. – Marek R Mar 14 '23 at 16:32
  • @MarekR: I must be blind... https://i.stack.imgur.com/TZuEk.png If you have some time, could you circle it for me? I hovered over every possible icon and dropdownbox. – Thomas Weller Mar 14 '23 at 16:34
  • 1
    @ThomasWeller a sorry didn't provide full information. Note I used "execution only" mode. In assembly mode I do not see this option either. – Marek R Mar 14 '23 at 16:37
  • @MarekR size of `double` is the same on MSVC and gcc. Only `long double` has different size, unless you pass [`-mlong-double-64/128`](https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html) – phuclv Mar 14 '23 at 17:01
  • 1
    You should not use floating point in inherently integral problems. – molbdnilo Mar 14 '23 at 17:04

1 Answers1

2

Problem is this:

int remrt = pow(rem, (1.0/b));
...
int li = pow(a,(1.0/b));

Note floating point calculation are suffering from precision. Result is always rounded. Now you are using implicit conversion from double to int, this means rounding towards to zero.

So if one case result is 10.00001 this is will be rounded to 10, but if result is 9.99999999 which is close to desired result outcome of conversion will be 9!

Since there are small differences how compilers perform calculation you were unlucky and get a bit different result which was on other side of integer value.

So be careful when rounding floating point numbers. use std::round or add tolerance to conversion (epsilon). Or better find solution which do not require use of floating points.

Marek R
  • 32,568
  • 6
  • 55
  • 140
  • Thanks for the explanations Marek. It was very helpful. However, I tried to narrow down at which point wrong value is assigned. I found this. For b=2, remrt=9, rem=100: float test1 = pow(remrt,b); -> gives 81 and int test2 = pow(remrt,b); -> gives 81 as well. whereas float test1 = rem-pow(remrt,b); -> gives 19 and int test2 = rem-pow(remrt,b); -> gives 18 (which is unexpected). Since I was passing rem-pow(remrt,b) as argument, it passed 18 instead of 19. – CodeHackeRツ Mar 14 '23 at 17:29