So I´ve been trying to solve this problem, but I just can´t. The thing is, I put a number of row in triangle, (can be any random number/row) and the program should return the sum of the squares of all the coefficients in that row.
#include <stdio.h>
unsigned long sum_triangle(const int row);
int main(){
printf("%lu\n", sum_triangle(7));
// sum(7)....7 is number of row
return 0;
}
unsigned long sum_triangle(const int row){
unsigned long sum = 0;
int temp =0;
for (int line = 0; line <= row ; line++) {
for (int number = 0; number <= line ; number++){
if (line == row){
temp = THIS NEEDS TO BE COMBINED SOMEHOW(line , number);
sum += (temp * temp);
}
}
}
return sum;
}
Problem is in the "temp". I need to somehow combine row and number and thats it. Any help would be much appreciated.
There is a formula for the sum of squares of a row:
sum of row m squares = binomial(2m, m)
Thus all you need is to implement a proper binomial
that doesn't overflow on reasonably sized integers. Coincidentally that Wikipedia article already has an implementation in C. Combining it all together:
// from https://en.wikipedia.org/wiki/Binomial_coefficient
unsigned long binomial(unsigned long n, unsigned long k) {
unsigned long c = 1, i;
if (k > n-k)
k = n-k;
for (i = 1; i <= k; i++, n--)
c = c / i * n + c % i * n / i;
return c;
}
unsigned long sum_triangle(int m) {
return binomial(2*m, m);
}