Find All Factorial Numbers Less Than or Equal to n

Problem

A number n is called a factorial number if it is the factorial of a positive integer. For example, the first few factorial numbers are 1, 2, 6, 24, 120,

Given a number n, the task is to return the list/vector of the factorial numbers smaller than or equal to n.

Examples:

Example 1:

Input: n = 3
Output: 1 2
Explanation: The first factorial number is 1 which is less than equal to n. The second number is 2 which is less than equal to n,but the third factorial number is 6 which is greater than n. So we print only 1 and 2.

Example 2:

Input: n = 6
Output: 1 2 6
Explanation: The first three factorial numbers are less than equal to n but the fourth factorial number 24 is greater than n. So we print only first three factorial numbers.

Your task:

You don't need to read input or print anything. Your task is to complete the function rotate() which takes the array A[] and its size N as inputs and modify the array in place.

• Expected Time Complexity: $O(K)$, Where K is the number of factorial numbers.
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=n<=10^{18}$

Solution

Python

def factorialNumbers(self, n):
	factorial = 1
    factorials = []
    i = 1
    while factorial <= n:
        factorials.append(factorial)
        i += 1
        factorial *= i
    
    return factorials

Java

static ArrayList<Long> factorialNumbers(long n) {
    ArrayList<Long> factorials = new ArrayList<>();
    long factorial = 1;
    int i = 1;
    while (factorial <= n) {
        factorials.add(factorial);
        i++;
        factorial *= i;
    }
    return factorials;
}

C++

vector<long long> factorialNumbers(long long n) {
    vector<long long> factorials;
    long long factorial = 1;
    int i = 1;
    while (factorial <= n) {
        factorials.push_back(factorial);
        i++;
        factorial *= i;
    }
    return factorials;
}

C

long long factorialNumbers(long long n, long long *out, int *out_size) {
    long long factorial = 1;
    int i = 1;
    *out_size = 0;
    while (factorial <= n) {
        out[(*out_size)++] = factorial;
        i++;
        factorial *= i;
    }
    return factorial;
}

• Time Complexity: $O(K)$
• Auxiliary Space: $O(1)$