A good math problem.

Problem:You’re given the following sequence:Write an algorithm with complexity O( log(n) ) to get the value of S.Solutions:1) the naive algorithm with a complexity O(n)#include <iostream>

using namespace std;

int main() {
// read the value of “a” and “n”..
long long a, S, A;
int n, i;
cin >> a >> n;
int fct = 1;
S = 0, A = a;
for(i = 0; i < n; i++) {
S += (fct * A);
A *= a, ++fct;
}
cout << S << “n”;
}2) faster algorithm with time complexity O(log(n)):we can get the value of S using the following formula:here’s the code:#include <iostream>

using namespace std;

long long power(long long a, int p) { //this function complexity is O(log(n))
long long res = 1;
while(p) {
if(p & 1)
res *= a;
a *= a;
p >>= 1;
}
return res;
}
int main() {
// read the value of “a” and “n”..
long long a, S, An, An1;
int n;
cin >> a >> n;
if(a == 1)
S = (n * (n + 1)) >> 1;
else {
An = power(a, n); // value of a^n
An1 = An * a; // value of a^(n + 1)

S = (((a * (1 – An)) / (1 – a)) – n * An1) / (1 – a);
}
cout << S << “n”;
}here’s the proof of the above formula:This problem is an exercise in Competitive programming book Edition 3,page [193].

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *