Crypto Number (Digit Manipulation)

Problem Statement

A crypto number (also known as a narcissistic number or Armstrong number) is a number where the sum of its digits, each raised to the power of the total number of digits, equals the number itself.

For example, 153 is a crypto number because 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153.

Given an integer n, determine if it is a crypto number. As a follow-up, find all crypto numbers in a given range [lo, hi].

Example 1:

Input: n = 153
Output: true
Explanation: 1^3 + 5^3 + 3^3 = 153

Example 2:

Input: n = 370
Output: true
Explanation: 3^3 + 7^3 + 0^3 = 27 + 343 + 0 = 370

Example 3:

Input: n = 123
Output: false
Explanation: 1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36 ≠ 123

Constraints:

• 0 <= n <= 10^9
• For range query: 0 <= lo <= hi <= 10^9

Difficulty: Easy (single check), Medium (range query with optimization)

---

Pattern Recognition

• What is the input structure? A single integer or a range of integers.
• What are we optimizing? Efficiently checking a digit-based property. For range queries, avoiding redundant computation.
• What pattern does this fit? Digit manipulation — extract digits, compute a function of them, compare to the original number.
• Why does this pattern fit? The property depends solely on the digits and their count. This is a classic digit-decomposition problem.

---

Approach

Single Number Check — Direct Computation

Extract each digit, raise it to the power of the digit count, sum, and compare.

function isCrypto(n):
    digits = list of digits of n
    k = len(digits)
    return sum(d^k for d in digits) == n

Time: O(d) where d is the number of digits (at most 10 for n <= 10^9). Space: O(d).

Range Query — Brute Force

Check every number in [lo, hi].

function cryptoInRange(lo, hi):
    result = []
    for n in lo..hi:
        if isCrypto(n): result.append(n)
    return result

Time: O((hi - lo) * d) — up to 10^9 * 10 = 10^10. Too slow. Why insufficient: Checking every number in a large range is impractical.

Range Query — Precomputation

Key Insight: There are very few crypto/narcissistic numbers. For numbers up to 10^9 (at most 10 digits), there are only 88 narcissistic numbers in total. You can either precompute all of them or observe that for a given digit count k, the maximum possible sum is k * 9^k. If k * 9^k has fewer than k digits, no k-digit crypto number exists. This caps the search.

Step-by-step:

1. For each digit count k from 1 to 10:
   • Generate all k-digit numbers? Too many. Instead, observe that the sum of digits^k is bounded by k * 9^k.
   • For k = 1: all single digits (0-9) are trivially crypto numbers.
   • For larger k: iterate candidates or use the known list.
2. Alternatively, since the total count is small (88 numbers up to ~39 digits), precompute all and filter by range.

For interview purposes, the key is the single-number check and understanding why there are so few crypto numbers.

---

Walkthrough

Checking n = 9474:

Step	Action	State
1	Extract digits	[9, 4, 7, 4]
2	Count digits	k = 4
3	Compute 9^4	6561
4	Compute 4^4	256
5	Compute 7^4	2401
6	Compute 4^4	256
7	Sum	6561 + 256 + 2401 + 256 = 9474
8	Compare to n	9474 == 9474 → True

Checking n = 100:

Step	Action	State
1	Extract digits	[1, 0, 0]
2	Count digits	k = 3
3	Compute 1^3 + 0^3 + 0^3	1 + 0 + 0 = 1
4	Compare to n	1 ≠ 100 → False

---

Implementation

TypeScript

function isCryptoNumber(n: number): boolean {
    if (n < 0) return false;

    // Convert to string to get digits and count
    const s = String(n);
    const k = s.length;

    // Sum each digit raised to the power of digit count
    let total = 0;
    for (const ch of s) {
        total += Math.pow(Number(ch), k);
    }

    return total === n;
}

function cryptoNumbersInRange(lo: number, hi: number): number[] {
    // All narcissistic numbers up to 10^9
    const known = [
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
        153, 370, 371, 407,
        1634, 8208, 9474,
        54748, 92727, 93084,
        548834,
        1741725, 4210818, 9800817, 9926315,
        24678050, 24678051, 88593477,
        146511208, 472335975, 534494836, 912985153,
    ];

    return known.filter(n => n >= lo && n <= hi);
}

function isCryptoNumberNoString(n: number): boolean {
    if (n < 0) return false;

    // Count digits
    let temp = n;
    let k = 0;
    while (temp > 0) {
        k++;
        temp = Math.floor(temp / 10);
    }
    if (n === 0) k = 1;

    // Sum digit^k
    temp = n;
    let total = 0;
    while (temp > 0) {
        const digit = temp % 10;
        total += Math.pow(digit, k);
        temp = Math.floor(temp / 10);
    }

    return total === n;
}

C++

bool isCryptoNumber(int n) {
    if (n < 0) return false;

    // Convert to string to get digits and count
    string s = to_string(n);
    int k = s.size();

    // Sum each digit raised to the power of digit count
    long long total = 0;
    for (char ch : s) {
        total += (long long)pow(ch - '0', k);
    }

    return total == n;
}

vector<int> cryptoNumbersInRange(int lo, int hi) {
    // All narcissistic numbers up to 10^9
    vector<int> known = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
        153, 370, 371, 407,
        1634, 8208, 9474,
        54748, 92727, 93084,
        548834,
        1741725, 4210818, 9800817, 9926315,
        24678050, 24678051, 88593477,
        146511208, 472335975, 534494836, 912985153,
    };

    vector<int> result;
    for (int n : known) {
        if (n >= lo && n <= hi) result.push_back(n);
    }
    return result;
}

bool isCryptoNumberNoString(int n) {
    if (n < 0) return false;

    // Count digits
    int temp = n, k = 0;
    while (temp > 0) {
        k++;
        temp /= 10;
    }
    if (n == 0) k = 1;

    // Sum digit^k
    temp = n;
    long long total = 0;
    while (temp > 0) {
        int digit = temp % 10;
        total += (long long)pow(digit, k);
        temp /= 10;
    }

    return total == n;
}

Watch out:

1. Handling n = 0. Zero has 1 digit, and 0^1 = 0, so 0 is a crypto number. Make sure your digit-counting logic handles this (the while loop would give k = 0 for n = 0).
2. Using int() conversion vs modular arithmetic. The string approach is cleaner in Python, but the interviewer may ask for the math-only approach using % 10 and // 10. Be ready with both.
3. Negative numbers. The definition typically applies only to non-negative integers. Return False for negative inputs.

---

Complexity Analysis

	Time	Space
Single check	O(d) where d = number of digits	O(d) or O(1)
Range (brute force)	O((hi - lo) * d)	O(1)
Range (precomputed)	O(1) lookup + O(k) filtering where k = 32 known numbers	O(1)

Bottleneck: The single check is inherently O(d) — you must examine every digit. For range queries, the insight that there are only ~32 crypto numbers below 10^9 makes precomputation the clear winner.

---

Edge Cases

1. n = 0 — Is a crypto number (0^1 = 0). Ensure your digit count handles zero.
2. Single-digit numbers (1-9) — All are crypto numbers since d^1 = d.
3. n = 10 — Not a crypto number: 1^2 + 0^2 = 1 ≠ 10.
4. Very large numbers near 10^9 — The exponentiation 9^10 is large but fits in Python's arbitrary-precision integers. In other languages, check for overflow.
5. Range with no crypto numbers — e.g., [10, 152]. Return empty list.
6. Negative input — Return False.

---

Related Problems

• LC 258 — Add Digits — Digit manipulation: repeatedly sum digits until single digit. Related digit-decomposition pattern.
• LC 202 — Happy Number — Repeatedly sum squares of digits. Similar digit extraction + cycle detection.
• LC 9 — Palindrome Number — Another digit property check using modular arithmetic.
• LC 1015 — Smallest Integer Divisible by K — Number theory with digit/modular reasoning.

---

What is Expected at Each Level

Junior: Implement the single-number check using string conversion. Explain the definition clearly. Handle basic edge cases like 0 and single digits.

Mid-level: Implement both string and math-only versions. Discuss why brute-force range search is impractical. Know that narcissistic numbers are rare and suggest precomputation for range queries.

Senior: Immediately note the finiteness of narcissistic numbers. Discuss the mathematical proof for the upper bound (for k digits, k * 9^k must have at least k digits — this fails beyond ~39 digits). Extend to related problems: happy numbers, digital roots, Kaprekar numbers. Discuss generating all narcissistic numbers programmatically using combinatorial digit enumeration.