algoadvance

A number is called a Harshad number (or Niven number) if it is divisible by the sum of its digits. Given a positive number num, write a function to determine if the number is a Harshad number.

Clarifying Questions

1. Range of Input
   • What is the range of num? Are we dealing with 32-bit integers only?
     • Assumption: We will assume that num is a positive integer and fits within the 32-bit integer range.
2. Output Format
   • Should the output be a boolean value (True or False)?
     • Assumption: Yes, we should return True if num is a Harshad number, otherwise False.
3. Examples
   • Can you provide a few examples to better understand the problem?
     • Sure:
       • Input: 18 -> Output: True (since 1 + 8 = 9 and 18 is divisible by 9)
       • Input: 19 -> Output: False (since 1 + 9 = 10 and 19 is not divisible by 10)

Strategy

1. Calculate Sum of Digits:
   • Convert the number to its string representation to easily access each digit.
   • Sum the digits of the number.
2. Check Divisibility:
   • Check if the original number is divisible by the sum of its digits.
3. Return Result:
   • Return True if the number is divisible by the sum of its digits, otherwise return False.

Code

def is_harshad_number(num):
    # Step 1: Calculate the sum of digits
    sum_of_digits = sum(int(digit) for digit in str(num))
    
    # Step 2: Check if the number is divisible by the sum of its digits
    return num % sum_of_digits == 0

# Test examples
print(is_harshad_number(18))  # True
print(is_harshad_number(19))  # False
print(is_harshad_number(21))  # True
print(is_harshad_number(1729))  # True

Time Complexity

• Time Complexity: O(d), where d is the number of digits in the input number num.
  • Calculating the sum of digits involves iterating through each digit, so the time complexity depends on the number of digits.
• Space Complexity: O(1), assuming the space needed to store the sum of digits and the result is constant and doesn’t scale with the size of the input.

The provided solution is efficient given the constraints and should work well for numbers within the typical 32-bit integer range.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?