Untitled

class Solution {
public:
    bool isDigitorialPermutation(int n) {
                
        // digitFrequency -> stores frequency of digits in original number
        // factorialDigitFrequency -> stores frequency of digits in computed factorial sum
        map<int, int> digitFrequency, factorialDigitFrequency;
        
        int tempNumber = n;
        
        // Count digit frequency of original number
        while (tempNumber > 0) {
            int digit = tempNumber % 10;
            digitFrequency[digit]++;
            tempNumber /= 10;
        }
        
        int factorialSum = 0;
        
        // Compute sum of factorials of digits
        for (auto entry : digitFrequency) {
            int digit = entry.first;
            int frequency = entry.second;
            
            int factorialValue = 1;
            
            // Compute digit!
            for (int i = digit; i >= 1; i--) {
                factorialValue *= i;
            }
            
            // Multiply by how many times this digit appears
            factorialSum += factorialValue * frequency;
        }
        
        int computedNumber = factorialSum;
        
        // Count digit frequency of factorial sum result
        while (computedNumber > 0) {
            int digit = computedNumber % 10;
            factorialDigitFrequency[digit]++;
            computedNumber /= 10;
        }
        
        // Compare both digit frequency maps
        // If identical, some permutation forms a digitorial number
        bool isValidPermutation = true;
        
        for (auto entry : digitFrequency) {
            if (entry.second != factorialDigitFrequency[entry.first]) {
                isValidPermutation = false;
                break;
            }
        }
        
        for (auto entry : factorialDigitFrequency) {
            if (entry.second != digitFrequency[entry.first]) {
                isValidPermutation = false;
                break;
            }
        }
        
        return isValidPermutation;
    }
};

/*
Time Complexity (TC):

Let d = number of digits in n (maximum 10 since n <= 10^9)

- Counting digit frequency: O(d)
- Computing factorial for digits (0–9 max): O(9) ≈ O(1)
- Building frequency of factorialSum: O(d)
- Comparing maps: O(10) ≈ O(1)

Overall TC = O(d) ≈ O(1) (since digits are bounded by 10)

Space Complexity (SC):

- Two maps storing digit frequencies (at most 10 entries each)

SC = O(1)
*/©leetcode