Optimised Approach needed

help
1

I need suggestion to optimise the solution of the problem in which we have to find the minimum number X such that sum of the number of factors from 1 to X is greater than or equal to K

for eg:
if k = 5
no. of factors of 1 =1
no. of factors of 2 = 2
no. of factors of 3 = 2
Therefore the answer will be 3.

Contsraints for K:10000000

I tried solving by calculating the no of factors from 1 and looping while the sum of no of factors is less than K .But i am getting time limit exceeded.
What will be the efficient approach to this problem?

Thank You

2

have you tried precomputing the results?

3

Yes i have precomputed the cumulative sum of the number of factors of size 10000.I couldn’t create the array of size > 10000 as it was giving time limit exceeded.
My array looked like:
1 3 5 8 10…

4

Can you share question link?

1 Like
5

I dont have the question link.
It was asked on a company’s organised contest hosted by hackerearth. They dont save the question.

6

Solved very easily see -

#include<bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 10000050
#define lli long  int
#define loop(i,n) for (lli i = 0; i < n; i++)
lli spf[MAX+1];

void sieve2(){ //smallest prime factor of N.

    loop(i,MAX+1) spf[i]=i;
    for(lli i=4;i<=MAX;i+=2) spf[i]=2;

    for(lli i=3; i*i<=MAX; i++){
        if (spf[i] == i){
            for (int j=i*i; j<=MAX; j+=i)
                if (spf[j]==j) //marking spf[j] if it is not previously marked
                    spf[j] = i;
        }
    }
}



lli tfactor[MAX+1];
lli sumfactor[MAX+1];
lli pre[MAX+1];
void sieve4(){ // totalfactor and sum_of_all_factors
    // n = (a^p)*(b^q)*(c^r)....
    // totalfactors = (p+1)*(q+1)*(r+1)...
    // sumoffactors =  [(a^(p+1)-1)/(a-1))]*[(b^(q+1)-1)/(b-1))]*[(c^(r+1)-1)/(c-1))]....
    sieve2();
    tfactor[1] = sumfactor[1] = pre[1] = 1;
    for(lli i=2;i<=MAX;i++){
        lli mspf = spf[i];
        lli prim = mspf;
        lli temp = i;
        lli cnt=0;
        while(temp%mspf==0){
            temp/=mspf;
            cnt+=1;
            prim = prim*mspf;
        }
        tfactor[i] = (cnt+1) * tfactor[temp];
        pre[i] = pre[i-1] + tfactor[i];
        sumfactor[i] = (prim -1)/(mspf-1) * sumfactor[temp];
     }
}

Now for each No. N (in query ) find the smallest index i such that pre[i]>= N , and how can i do this … we can do binary search here :slight_smile:

int main(){
sieve4();
lli t;
cin>>t;
while(t--) {
    lli n;
    cin>>n;
    lli ans = upper_bound(pre,pre+MAX,n) - pre;
    cout<<ans-1<<endl;
  }
return 0;
}
1 Like
7

Which company test ?

8

Thanks man

1 Like
9

Accenture. It was an invite only contest.

10

should i tell u basic idea of my code or my code is enough (as i wrote comments )

11

from sys import stdin,stdout
import math
def countdivisor(n):
cnt=0
for i in range(1,(int)(math.sqrt(n))+1):
if n%i==0:
if n/i==i:
cnt=cnt+1
else:
cnt=cnt+2
return cnt
def solve(k):
if(k==0):
return 0
if k==1:
return 1
for i in range(10000):
if(a[i]>=k):
break
return i
a=[0,1]
for i in range(2,10000):
a.append(a[i-1]+countdivisor(i))
for i in range(int(stdin.readline())):
k=int(stdin.readline())
print(solve(k))

can u tell what is wrong in my program it give TLE on 0<k<10^7

12

obvioulsly your approach get tle …format your code :slight_smile: