DSA 450 Notes

Problem Statement

Given a positive integer n, find the factorial of n. For large numbers, the result won't fit in standard data types, so store it in an array or string.

Example:

Input: n = 100
Output: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Approach 1: Using Array Multiplication (Brute Force)

Intuition

Simulate multiplication the way we do it by hand - multiply each digit and handle carry.

Algorithm

Store result in an array where each element is a single digit
For each number from 2 to n:
- Multiply each digit by the current number
- Handle carry appropriately
Result array contains digits in reverse order

java

import java.util.*;

public class Solution {
    public String factorialBruteForce(int n) {
        if (n == 0 || n == 1) return "1";
        
        List<Integer> result = new ArrayList<>();
        result.add(1);
        
        for (int x = 2; x <= n; x++) {
            int carry = 0;
            
            // Multiply each digit by x
            for (int i = 0; i < result.size(); i++) {
                int prod = result.get(i) * x + carry;
                result.set(i, prod % 10);
                carry = prod / 10;
            }
            
            // Handle remaining carry
            while (carry > 0) {
                result.add(carry % 10);
                carry /= 10;
            }
        }
        
        // Convert to string (reverse order)
        StringBuilder ans = new StringBuilder();
        for (int i = result.size() - 1; i >= 0; i--) {
            ans.append(result.get(i));
        }
        
        return ans.toString();
    }
}

Complexity Analysis

Time Complexity: O(n² × d) where d is the number of digits in result
Space Complexity: O(d) - Storing the result digits

Approach 2: Optimized Array Multiplication

Intuition

Instead of storing single digits, store larger chunks (like 4 digits per element) to reduce operations.

Algorithm

Use base 10000 instead of base 10
Each array element holds up to 4 digits
Perform same multiplication with optimized chunk size

java

import java.util.*;
import java.math.BigInteger;

public class Solution {
    public String factorialOptimized(int n) {
        if (n == 0 || n == 1) return "1";
        
        final int BASE = 10000;  // Store 4 digits per element
        List<Long> result = new ArrayList<>();
        result.add(1L);
        
        for (int x = 2; x <= n; x++) {
            long carry = 0;
            
            for (int i = 0; i < result.size(); i++) {
                long prod = result.get(i) * x + carry;
                result.set(i, prod % BASE);
                carry = prod / BASE;
            }
            
            while (carry > 0) {
                result.add(carry % BASE);
                carry /= BASE;
            }
        }
        
        // Convert to string
        StringBuilder ans = new StringBuilder();
        ans.append(result.get(result.size() - 1));  // First chunk
        
        for (int i = result.size() - 2; i >= 0; i--) {
            String chunk = String.format("%04d", result.get(i));
            ans.append(chunk);
        }
        
        return ans.toString();
    }
    
    // Using BigInteger
    public String factorialBigInteger(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n² × d/k) where k is digits per chunk (4 in this case)
Space Complexity: O(d/k) - Reduced array size

Approach 3: Using Prime Factorization

Intuition

Count the power of each prime in n! and multiply them together. This is more efficient for very large n.

Visual Example

For n = 5 (5! = 120):

Initial: result = [1]

x = 2: 
  1 × 2 = 2, carry = 0
  result = [2]

x = 3:
  2 × 3 = 6, carry = 0
  result = [6]

x = 4:
  6 × 4 = 24
  24 % 10 = 4, carry = 2
  result = [4]
  Add carry: result = [4, 2]

x = 5:
  4 × 5 + 0 = 20, 20 % 10 = 0, carry = 2
  2 × 5 + 2 = 12, 12 % 10 = 2, carry = 1
  result = [0, 2]
  Add carry: result = [0, 2, 1]

Final (reversed): "120"

Properties of Factorial

Number of trailing zeros in n! = count of factor 5 in n!
- Formula: ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...
Number of digits in n! ≈ log₁₀(n!) + 1
- Using Stirling's approximation: n! ≈ √(2πn) × (n/e)^n

Key Takeaways

Array-based multiplication is essential when result exceeds standard data types
Using larger base (like 10000) reduces number of operations
Handle carry propagation carefully in multiplication
For languages with big integers (Python, Java BigInteger), use built-in support
Prime factorization approach is theoretically more efficient for very large n
Trailing zeros problem is a common related question

Find factorial of a large number

Problem Statement

Approach 1: Using Array Multiplication (Brute Force)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimized Array Multiplication

Intuition

Algorithm

Complexity Analysis

Approach 3: Using Prime Factorization

Intuition

Visual Example

Properties of Factorial

Key Takeaways