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

general
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
75

@l_returns . What will be the complexity to generate all the distinct divisor from it prime factors and there exponents ?

76

O(no. of divisors) \hspace{0mm}

1 Like
77

Ok , so i use sqrt(n) method to do the factorization of a number , it will be more efficient for composite number as the number is itself is decreasing by the factor of prime , but what if the number is itself prime . Here is my pseudo code for prime factorization fQZFMk - Online C++0x Compiler & Debugging Tool - Ideone.com . Also can you give me a snippet of code . How to generate factors usinf pf. I am keen to do this problem using that . Problem - D - Codeforces . Thanx for your help .

78

Can you explain me your code , how you find max divisor till 1e15 ? .

79

This might be greater than O(no. of divisors) but what I suggested takes exactly steps=no. of divisors.

81

Will not the worst time will be sqrt(n) for prime factorization too , if a number is prime itself . The codeforces problem i mentioned you , i can use sieve to get all the prime factors in logn time , but i don’t know how to generate all the divisor using that .

1 Like
82

you can make divisors of all numbers as well using sieve. loop will be same except if condition.

83

yes i know that , i also made the accepted solution using that , but i am interested in getting divisor of a number using pf .

84

Okay thenI try dividing that number with prime numbers which are less than sqrt(value).
If we do brute force loop till sqrt(N) then complexity is sqrt(N). but If we just check primes less than sqrt(N) then it is O(sqrt(N)/10) this was my hack. I think this might not be the official soln.
Hence execution time might reduce to /10.