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

general
42

But it accepted bro , and in c language the brute force order of n complexity is accepted bro

43

Wtf. Isn’t this O(n)
R u using supercomputers ? :stuck_out_tongue:

1 Like
44

Ya it’s o(n) I said that in c o(n) is accepted and in cpp something optimize sqrt(n) approach is accepted…
Ya I have supercomputer …lol :joy::joy:
Codevita is just language game , c me kro o(n2) accepted in cpp o(n) give tle in Python o(sqrt(n)) gives tle ,wtf … codevita sucks today

2 Likes
45

Bro there is a question called similar char in which a string is given and we have to process q queries
In which query user give index we have to count total number of occurrences before given index of the given character
Ex s= “abaaaba”
Index =3
Now at index the character is a , total number of a before third index is 2 so we have to print two
Can u tell me your approach.

46

Oh, my bad, u said this in another above statement. :smile:

1 Like
47

I was telling that finding all prime factors will take worst case sqrt(n). Correct me if I’m wrong?

48

Nope
It will take less than sqrt(n) because primes less than sqrt(n) are sqrt(n)/10 in worst case.

49

I didn’t understand what and how are you saying. Can you explain it a bit considering n=10^15.

50

I have precomputed all prime numbers less than sqrt(10^15) .
Now in each test case for given N
I will iterate through all primes less than sqrt(n).
Now primes less than sqrt(n) wont be more than sqrt(n)/10. Hence it will take 1/10th time.

51

How can you precompute factor as prime factor of different number is different, you have to compute prime factor for each number separately right?

52

Edited. I meant prime numbers.

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