Taro Logo

Armstrong Number

Easy
Amazon logo
Amazon
1 view

Given a non-negative integer, determine whether it is an Armstrong number.

An Armstrong number is a number that is equal to the sum of its own digits raised to the power of the number of digits. For example, 153 is an Armstrong number because 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153. Similarly, 1634 is an Armstrong number because 1^4 + 6^4 + 3^4 + 4^4 = 1 + 1296 + 81 + 256 = 1634.

Write a function to determine if a given integer is an Armstrong number. Your function should take a non-negative integer as input and return true if it is an Armstrong number, and false otherwise.

Here are a few examples:

  • isArmstrong(153) should return true
  • isArmstrong(123) should return false
  • isArmstrong(0) should return true
  • isArmstrong(1) should return true
  • isArmstrong(1634) should return true

Consider edge cases such as zero and single-digit numbers. How can you efficiently compute the power of each digit without using built-in exponentiation functions in some cases? What is the time and space complexity of your approach?

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum possible value of the input number?
  2. Is the input guaranteed to be a non-negative integer?
  3. Could you define more precisely what you mean by 'Armstrong number'? Specifically, how is the number of digits determined when calculating the sum of digits raised to that power?
  4. Should I return a boolean value indicating whether the number is an Armstrong number, or something else?
  5. Are there any specific error conditions I should handle, such as if the input is of an incorrect type?

Brute Force Solution

Approach

To find an Armstrong number the brute force way, we'll check every number within a given range to see if it meets the Armstrong criteria. For each number, we calculate the sum of its digits raised to the power of the number of digits, then compare the sum to the original number.

Here's how the algorithm would work step-by-step:

  1. Start with the first number in the range.
  2. Figure out how many digits this number has.
  3. Take each digit and raise it to the power of the number of digits.
  4. Add up all those results together.
  5. Check if the sum you calculated is the same as the original number.
  6. If they match, you've found an Armstrong number! If not, it's not an Armstrong number.
  7. Move on to the next number in the range and repeat the process from the second step.
  8. Keep doing this until you've checked every number in the range.

Code Implementation

def find_armstrong_numbers(start_range, end_range):
    armstrong_numbers = []
    for current_number in range(start_range, end_range + 1):

        number_string = str(current_number)
        number_of_digits = len(number_string)
        sum_of_powers = 0

        # Iterate through digits to calculate the sum of powers
        for digit_char in number_string:
            digit = int(digit_char)
            sum_of_powers += digit ** number_of_digits

        # Verify if the number is an Armstrong number
        if current_number == sum_of_powers:

            # Add the Armstrong number to the list
            armstrong_numbers.append(current_number)

    return armstrong_numbers

def is_armstrong_number(number_to_check):
    number_string = str(number_to_check)
    number_of_digits = len(number_string)
    sum_of_powers = 0

    # Iterate through digits to calculate the sum of powers
    for digit_char in number_string:
        digit = int(digit_char)
        sum_of_powers += digit ** number_of_digits

    #Return if Armstrong number
    return number_to_check == sum_of_powers

def get_armstrong_numbers_in_range(start_number, end_number):
    list_armstrong_numbers = []
    for number in range(start_number, end_number + 1):

        # Check each number in range
        if is_armstrong_number(number):
            list_armstrong_numbers.append(number)

    #Return the list of Armstrong numbers
    return list_armstrong_numbers

Big(O) Analysis

Time Complexity
O(n*d)Given a range of numbers up to n, we iterate through each number to check if it's an Armstrong number. For each number, we determine the number of digits (d) and then perform calculations based on these digits. The number of digits (d) affects the computation cost for each number we analyze up to n. Therefore the time complexity is approximately proportional to n multiplied by d. Since d is bounded by log(n), it may be tempting to simplify it to O(n log n); however, based on the explanation provided d is a constant factor of the number, leading to O(n*d).
Space Complexity
O(1)The algorithm calculates the number of digits, the power of each digit, and the sum of these powers. These calculations involve a few integer variables to store intermediate results like the digit count, individual digits, power calculations, and the overall sum. The space required for these variables remains constant regardless of the range size N, as the memory used doesn't scale with the input range. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

An Armstrong number is a number where the sum of its digits, each raised to the power of the number of digits, equals the original number. To efficiently check if a number is an Armstrong number, we need a two-step process. First determine the digit count, and then sum the digits raised to that power, finally compare the sum with the original number.

Here's how the algorithm would work step-by-step:

  1. First, count how many digits are in the given number.
  2. Next, take each digit of the number and raise it to the power of the digit count you found in the first step.
  3. Add up all the results from the power calculations in the previous step.
  4. Finally, check if the sum is equal to the original number. If they are equal, the number is an Armstrong number.

Code Implementation

def is_armstrong_number(number):
    number_string = str(number)
    number_of_digits = len(number_string)

    # Need digit count for raising each digit to its power

    sum_of_powers = 0

    for digit_char in number_string:
        digit = int(digit_char)
        sum_of_powers += digit ** number_of_digits

    # Compare sum with original number

    if sum_of_powers == number:
        return True
    else:
        return False

def main():
    test_number_one = 153
    test_number_two = 120

    # Test case to confirm functionality

    is_armstrong_one = is_armstrong_number(test_number_one)
    is_armstrong_two = is_armstrong_number(test_number_two)
    print(f'{test_number_one} is Armstrong: {is_armstrong_one}')
    print(f'{test_number_two} is Armstrong: {is_armstrong_two}')

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity
O(log n)The time complexity is determined by the number of digits in the input number n. Counting the digits involves a logarithmic operation related to the base 10 logarithm of n. Similarly, iterating through the digits to calculate the sum of powers also depends on the number of digits. Therefore, both steps are proportional to the number of digits, which is log base 10 of n. Thus, the overall time complexity is O(log n).
Space Complexity
O(1)The space complexity is O(1) because the algorithm uses a fixed number of variables (to store the original number, the digit count, a sum, and the individual digits) regardless of the size of the input number. No auxiliary data structures like lists or hash maps are created that scale with the input. The memory usage remains constant as the input number increases.

Edge Cases

CaseHow to Handle
Input is a negative numberReturn false, since Armstrong numbers are defined for non-negative integers only.
Input is zeroReturn true, as 0 is considered an Armstrong number for a power of 1 (0^1 = 0).
Single-digit number (0-9)Return true, as any single-digit number is an Armstrong number (e.g., 5^1 = 5).
Large integer input leading to potential overflow during power calculationUse a data type that supports larger numbers or check for overflow before returning the result, potentially returning false in case of overflow.
Input number is extremely large (e.g., close to the maximum integer value)Handle large input carefully by using appropriate data types and considering the performance implications of repeated exponentiation.
Input contains only the digit '1'The solution should correctly handle this, as the sum of powers will equal the original number.
Input is a floating-point number or stringCast it to an integer or return an error message/false since Armstrong numbers are integers.
Integer overflow during the sum of powered digitsUse a larger data type (e.g., long) or check for overflow during each digit power summation to prevent inaccurate results.