Algorythm to find factoradic for given number n which works in time O(log n)
0
I have just written a code which does its job, but I have to optimize it to work in time O(log n) . The problem is that I'm not sure whether its time complexity is good and if it's not, how should I fix it? Factoradic representation of a number is a sequence s k , s k-1 ... s 2 , s 1 that: -> n = 1! * s 1 + 2! * s 2 + ... + k! * s k -> s i ≤ for i ∈ {1, 2, ..., k} -> s k > 0 -> eg. 107 = 4! * 4 + 3! * 1 + 2! * 2 + 1! *1 My code: unsigned long long int n; unsigned long long int maxFact[21] = {0}; maxFact[0] = 1; maxFact[1] = 1; cout<<"Insert n: "; cin >> n; int i = 2; while (maxFact[i-1] * i <= n) // find higher factorial <= n { maxFact[i] = maxFact[i-1] * i; i++; } cout << "Factoradic representati