Print All Divisors of Number in Increasing Order (Code Vita)

general
53

Ohh, now it’s clear. If it’s prime number(not prime factor) then u can precompute using sieve. Nice :slight_smile:

54

One more doubt: Will nloglogn sieve work for that, or we have to use O(n) sieve as sqrt(n) will be between 10^7 and 10^8

55

It would be around 3.2*10^7 and loglog(n) is 4+
It would be tough if time limit is tight but it’s better than T*sqrt(10^{15}) at least.
3 times faster.
PS : idk what was time limit in contest.

56

Hmm,that was the main issue, they didn’t provide time limit(atleast I didn’t see anywhere in problem statement :smile:)

57

why can’t use a simple for loop to print all the divisor ???

58

find prefix sums (frequency of each char upto index i) then
u can answer each query in O(1)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
int pre[n+1][26];
for(int i=0;i<=n;i++)
for(int j=0;j<26;j++)
pre[i][j]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<26;j++)
pre[i][j]=pre[i-1][j];

    pre[i][s[i-1]-'a']++;
}
int q;
cin>>q;
while(q--)
{
    int x;
    cin>>x;
    cout<<pre[x-1][s[x-1]-'a'];
}

}
time complexity: O(n*26+q)

59

#include <stdio.h>
int main()
{
int test;
scanf("%d",&test);
for(int j=0; j<test ; j++)
{
long long int number, i;
scanf("%lld",&number);
for(i=1; i <= number; ++i)
{
if (number%i == 0)
{
printf("%lld “,i);
}
}
printf(”\n");
}
return 0;
}
i did this and it got AC

60

Before codevita: Need to use an optimized algorithm if it’s giving TLE.

After codevita: Just use C :stuck_out_tongue:

62

@l_returns I misunderstood ur approach earlier ,I thought that u r saying something similar to this

void precompute()
{
int minPrime[n + 1];
for (int i = 2; i * i <= n; ++i)
{
if (minPrime[i] == 0)
{
for (int j = i * i; j <= n; j += i)
{
if (minPrime[j] == 0)
minPrime[j] = i;
}
}
}

for (int i = 2; i <= n; ++i)
{
if (minPrime[i] == 0)
    minPrime[i] = i;
}

}

void primefactors(int n)
{
vector res;
while (n != 1)
{
res.push_back(minPrime[n]);
n /= minPrime[n];
}
}

ur solution seems to be working fine …!!! cheers >>>

1 Like
63

if N=40 then 2^3*5^1

count of divisors=(3+1)*(1+1)=8

divisors are as follows

  1. 2^0 * 5^0
  2. 2^0 * 5^1
  3. 2^1 * 5^0
  4. 2^1* 5^1
  5. 2^2 * 5^0
  6. 2^2 * 5^1
  7. 2^3* 5^0
  8. 2^3 * 5^1
2 Likes
64

Okay :slight_smile: \hspace{0mm}

65

No need to do this , I can do in O(n) complexity in cpp / Python (accepted) and again the basic brute Force o(n2) is accepted in C language.

67

O(n)…i am curious to know abt that…can u share ur approach pls

1 Like
68

I did the same thing but got run time error.

#include
#include
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long n,p,q,i,Q,res,j,ind;
string str;
cin>>n;
long fre[n][26];
for(j=0;j<26;j++)
fre[0][j]=0;
cin>>ws;
cin>>str;
fre[0][str[0]-‘a’]+=1;
for(i=1;i<n;i++)
{
ind=str[i]-‘a’;
for(j=0;j<26;j++)
fre[i][j]=fre[i-1][j];
fre[i][ind]++;

}
cin>>Q; 
while(Q--)
{
    res=0;
    cin>>q;
    ind=str[q-2]-'a';
    res=fre[q-2][ind];
    if(q==1)
        res=0;
    cout<<res<<endl;
}
return 0;

}

69

when q=1 you are trying to access str[-1] …

70

But it works when I check for q=1

Screenshot%20from%202019-07-14%2010-32-32
Screenshot from 2019-07-14 10-32-32.png1366×768 76.9 KB

71

You should write if(q==1) condition just after cin>>q; statement, because in case q=1; your program can throw a runtime exception due to accessing str[1-2]( for some ide). May be codechef ide is not throwing error, but codevita ide is different.

1 Like
72

Yes they judge C solutions in their Supercomputer …
and C++ and Python solutions in their mainframe

Looks like they have different test cases for different languages. :stuck_out_tongue:

73

I actually wrote same algorithm and submitted in python and C++
Guess what? My C++ didn’t give TLE but python did.
:slight_smile:

1 Like
74

i know everything bro , i solve almost 10 to 12 questions and u wiil be shocked that if a solution ives tle in python cpp java ruby then submit in C and boom it passes…LOL

1 Like