Can someone please explain what is wrong with my approach. An example n where it fails would be highly appreciated .
Code:
#include <bits/stdc++.h>
using namespace std;
int fact(int n){
int count =0;
for(int i= 1; i*i <= n; ++i){
if(n%i == 0){
if(i != n/i) count+=2;
else count++;
}
}
return count;
}
int main() {
int n;
cin>>n;
unsigned long long int count = 1;
if(n == 1) cout<<0;
else if(n == 2) cout<<1;
else{
int prev_fact = 2; //factors of 2 as we start from n = 3
for(int i = 3; i <= n; ++i){
//for each i find fact(i+1) + fact(i) -3
// -3 because
//1 is common factor(take it only once)
//i canāt be a solution
//i+1 canāt be a solution
int curr_fact = fact(i+1);
count += curr_fact + prev_fact -3;
prev_fact = curr_fact;
}
cout<<count;
}
return 0;
}
Link of my code: https://www.codechef.com/viewsolution/39919169
What I am doing here (in else part) is
Iterate i from 3 to n
and for each i
the answer accumulates as fact(i+1)+fact(i)-3
-3 because
1 is common (take it only once)
i canāt be a solution
i+1 canāt be a solution
For example n = 5
we start from
i = 1 => 0 (0 pairs possible)
i = 2 => 1 (1 pair possible)
so we directly initialize count = 0+1 = 1;
and from below the else part works
i = 3 => 2
count += f(4)+f(3) -3 = 3+2-3 = 2
i = 4 => 2
count += f(5) + f(4) -3= 2 + 3 -3 = 2
i = 5 => 3
count += f(6) + f(5) -3 = 4+2-3 = 3
(here f(x) = number of factors of x)
therefore the answer is 1+2+2+3 = 8
Can someone please explain where I am wrong/ give a test case where it fails?