Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an integer n, return true if and only if it is an Armstrong number. The k-digit number n is an Armstrong number if and only if the kth power of each digit sums to n.
Example 1:
Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 13 + 53 + 33.Example 2:
Input: n = 123
Output: false
Explanation: 123 is a 3-digit number, and 123 != 13 + 23 + 33 = 36.Constraints:
1 <= n <= 10^8Check if the given k-digit number equals the sum of the k-th power of it’s digits.
How to compute the sum of the k-th power of the digits of a number ? Can you divide the number into digits using division and modulus operations ?
You can find the least significant digit of a number by taking it modulus 10. And you can remove it by dividing the number by 10 (integer division). Once you have a digit, you can raise it to the power of k and add it to the sum.
Determine a Armstrong Number
The first task is to count how many digits of the given number, we can convert to string and use the len function:
1 2 | def numberOfDigits(n): return len(str(n)) |
def numberOfDigits(n): return len(str(n))
We can use math:
1 2 | def numberOfDigits(n): return int(math.log(n, 10)) + 1 |
def numberOfDigits(n): return int(math.log(n, 10)) + 1
Alternatively, we can count digit by digit:
1 2 3 4 5 6 | def numberOfDigits(n): ans = 0 while n: ans += 1 n //= 10 return ans |
def numberOfDigits(n): ans = 0 while n: ans += 1 n //= 10 return ans
The time complexity is O(log10(n)) or O(M) where M is the number of the digits.
Then, the next step is to sum the power of digits, which we can simply do this:
1 2 3 4 5 6 | def isArmsStrong(n): d = numberOfDigits(n) ans = 0 for i in str(n): ans += int(i) ** d return ans == n |
def isArmsStrong(n): d = numberOfDigits(n) ans = 0 for i in str(n): ans += int(i) ** d return ans == n
The ** operator is the power – for example, a**b is same as pow(a, b). We convert the number into the string and iterate over the digits. We can use one-liner:
1 2 3 | def isArmsStrong(n): d = numberOfDigits(n) return n == sum(int(i) ** d for i in str(n)) |
def isArmsStrong(n): d = numberOfDigits(n) return n == sum(int(i) ** d for i in str(n))
Another way is to iterate digits one by one from the right:
1 2 3 4 5 6 7 8 | def isArmsStrong(n): d = numberOfDigits(n) ans = 0 m = n while m: ans += (m % 10) ** d m //= 10 return m == ans |
def isArmsStrong(n): d = numberOfDigits(n) ans = 0 m = n while m: ans += (m % 10) ** d m //= 10 return m == ans
The same time complexity O(M) or O(Log10(N)).
See also: How to Determine the Armstrong Number?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: GoLang: Command Line Tool to Sort Strings
Next Post: Convert UTF-8 Char Array to Raw Byte Array in Java