0

It might not be like other asked questions in stackoverflow. In this problem, it works fine, but in one case, it returns wrong answer. I'm trying to solve the logical issue of this program.

I wrote a program to calculate the sum of this:

enter image description here

x, n, a would be entered by the user:

enter image description here

Here is my program: 

#include <iostream>
long long int unsigned fact (long long unsigned int a);
long long int unsigned comb (long long unsigned int n, long long unsigned int r);
long long unsigned intpower (long long unsigned int a, long long unsigned int n);
using namespace std;

int main()
{
    int n;
    long long unsigned int x, a;
    cin >> a >> x >> n;

    long long unsigned int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += comb(n, i)*intpower(x, i)*intpower(a, (n-i));
    }

    cout << sum;

    return 0;
}
// Calculates Factorial
long long int unsigned fact (long long unsigned int a) {

    long long int unsigned p = 1;

    for (long long unsigned int i = 1; i <= a; i++) {
        p *= i;
    }

    return p;
}
// Calculates the combination
long long int unsigned comb (long long unsigned int n, long long unsigned int r) {

    return (fact(n)/fact(r)/fact(n-r));
}
long long unsigned intpower (long long unsigned int a, long long unsigned int n){
    long long unsigned int p = 1;
    for (long long unsigned int i = 1; i <=n ; i++){
        p *= a;
    }
    return p;
}

But in one case, my program returns wrong answer. Here's the test done my a website that verifies the written programs for problems:

enter image description here

Do you guys have any idea why I got wrong answer in one test? The thing is I don't know what numbers would be entered in test 1, but there should be a logical issue that it gives wrong answer in one case.

Kind regards.

Alfredo Davnichi
  • 19
  • 3
  • 1
    Why don't you try it with several numbers and find out? Maybe there's an overflow bug - have you tried the highest allowed numbers? (n=10 x=1000000000 a=1000000000) – user253751 Dec 30 '19 at 13:56
  • 1
    First of all please don't show us images of text, copy-paste the text *as text* into the question instead. Secondly, unless you have the example input that give the wrong results it's going to be very hard to debug or replicate the problem. – Some programmer dude Dec 30 '19 at 13:57
  • @user253751 I've used long long unsigned int, should not get overflowed. – Alfredo Davnichi Dec 30 '19 at 13:57
  • @user253751 @Someprogrammerdude What if `long long unsigned int sum = 0` gets overflowed with large numbers? How can I fix the overflow issue? – Alfredo Davnichi Dec 30 '19 at 13:59
  • Maybe they're not expecting you to fix the overflow issue. Maybe the issue is a completely different issue. Or maybe it is the overflow issue. How can you fix it? Probably by finding a library that has bigger integers (like GMP). I wouldn't expect your professor to make you learn about that yet though. That's why I think there might be a problem different from overflow. – user253751 Dec 30 '19 at 14:06
  • @user253751 @Someprogrammerdude Let me ask my question in different way. How can I find the biggest `x` and `a`s with `n=10` that `sum` doesn't get overflowed? – Alfredo Davnichi Dec 30 '19 at 14:06
  • 2
    @AlfredoDavnichi Look at your `comb` function. Take out pencil and paper and do a combination calculation. Do you see that you are "cancelling out" a lot of values and not really doing straight factorials? Take that same approach in the `comb` function. – PaulMcKenzie Dec 30 '19 at 14:08
  • @PaulMcKenzie Factorial for numbers up to 10 should be fine as a `long long unsigned int`. – user253751 Dec 30 '19 at 14:09
  • Concerning what @PaulMcKenzie mentioned: Wikipedia mentions this as well: [Example of counting combinations](https://en.wikipedia.org/wiki/Combination#Example_of_counting_combinations). – Scheff's Cat Dec 30 '19 at 14:10
  • @Alfredo Davnichi The largest number you can hold is 2^(CHAR_BITS * sizeof(long long unsigned int))-1, a bit of algebra should show you what the largest x & a are. As noted above, you need to calculate things the smart way to avoid overflow along the way. – Uri Raz Dec 30 '19 at 14:11
  • 1
    Also there is this: `sum += comb(n, i)*pow(x, i)*pow(a, (n-i));`. Do not use `pow` here. [See this](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os). Usage of `pow` should be reserved for fractional exponents and for the case where the final result will be larger than what fits in a `long long`. – PaulMcKenzie Dec 30 '19 at 14:11
  • @PaulMcKenzie Ok, so I remove the pow function from cmath library and write a function myself. Right? – Alfredo Davnichi Dec 30 '19 at 14:18
  • @AlfredoDavnichi Yes, you should write your own `pow` function. You can use the [method of squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring). – PaulMcKenzie Dec 30 '19 at 14:19
  • @PaulMcKenzie Writing my own power function didn't help, I will update the code in the question. – Alfredo Davnichi Dec 30 '19 at 14:30
  • @PaulMcKenzie 1. Would you please give me a link to help me understand how to use GMP to avoid getting overflowed, please? 2. What's the largest number GMP can hold? – Alfredo Davnichi Dec 30 '19 at 14:42
  • You can simply use [boost multiprecision](https://www.boost.org/doc/libs/1_62_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html). Here is your code using [128 bit integers](https://coliru.stacked-crooked.com/a/986b888f39620eda) – PaulMcKenzie Dec 30 '19 at 14:44
  • @PaulMcKenzie Unknown directory error. Where should I download it from? – Alfredo Davnichi Dec 30 '19 at 14:53
  • [Boost website](https://www.boost.org/). Also, are you trying to answer a question from one of those "online judge" websites? If so, then maybe the question you're being asked is not easily solvable using standard C++, since the data types used are "big integer" types. Languages like Java have big integer types. – PaulMcKenzie Dec 30 '19 at 14:59
  • 1
    Why not simply implementing (x+a)^n ? – Damien Dec 30 '19 at 15:11

1 Answers1

0

As the comments have pointed, the failing test case is most probably because of a corner-side with the maximum values of the inputs. The range that you can store in a long long int data type (if your compiler support the type) is from -9,223,372,036,854,775,807 to 9,223,372,036,854,775,807. It means that if in your case you have x, a and n as their maximum values, you will have an overflow. For an example, the output of your code with the following inputs is the same:

for:

int n = 10;
long long unsigned int x = 9999999999;
long long unsigned int a = 1000000000;

output is: 9223372036854775808

int n = 10;
long long unsigned int x = 1000000000;
long long unsigned int a = 1000000000;

the output is again: 9223372036854775808

TonySalimi
  • 8,257
  • 4
  • 33
  • 62
  • You've used ten digit-numbers for x/a. The max is 10^9 like 999,999,999. Btw, it might not be the problem. Does using GMP library fix the issue? – Alfredo Davnichi Dec 30 '19 at 14:20
  • @AlfredoDavnichi In the problem assumptions, you have mentioned that `1 <= x,a <= 10^9`. So, it means that the maximum value for `a` and `x` will be 1000000000. BTW, I believe that if you use specific libraries such as GMP, it will solve your problem. – TonySalimi Dec 30 '19 at 14:26