Jobs

Interviews

Discussions

Harshad Number

Easy

Asked by:

3 views

An integer divisible by the sum of its digits is said to be a Harshad number. You are given an integer x. Return the sum of the digits of x if x is a Harshad number, otherwise, return -1.

Example 1:

Input: x = 18

Output: 9

Explanation:

The sum of digits of x is 9. 18 is divisible by 9. So 18 is a Harshad number and the answer is 9.

Example 2:

Input: x = 23

Output: -1

Explanation:

The sum of digits of x is 5. 23 is not divisible by 5. So 23 is not a Harshad number and the answer is -1.

Constraints:

1 <= x <= 100

Try coding it in LeetCode

Harshad Number

Easy

Asked by:

3 views

Example 1:

Input: x = 18

Output: 9

Explanation:

The sum of digits of x is 9. 18 is divisible by 9. So 18 is a Harshad number and the answer is 9.

Example 2:

Input: x = 23

Output: -1

Explanation:

The sum of digits of x is 5. 23 is not divisible by 5. So 23 is not a Harshad number and the answer is -1.

Constraints:

1 <= x <= 100

Try coding it in LeetCode

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:

What is the expected range for the input integer n? Specifically, what is the maximum possible value of n?
Is zero considered a Harshad number? How should I handle the case when n is 0?
The problem states 'non-negative integer', so negative numbers are not valid inputs, correct?
Are we concerned about potential integer overflow issues when calculating the sum of digits?
Are there any specific performance expectations or limitations I should be aware of beyond standard optimization practices?

Brute Force Solution

Approach

The Harshad Number problem asks if a number is divisible by the sum of its digits. The brute force way is simply to calculate the digit sum and then check divisibility.

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

First, take the number you are given.
Next, find the sum of all its digits.
Finally, see if the original number can be divided evenly by the sum of its digits, with no remainder.

Code Implementation

def is_harshad_number(number_to_check):
    number_string = str(number_to_check)
    sum_of_digits = 0

    for digit_character in number_string:
        digit = int(digit_character)
        sum_of_digits += digit

    # Handle cases to avoid division by zero
    if sum_of_digits == 0:
        return False

    # Check if the number is divisible by the sum of its digits
    if number_to_check % sum_of_digits == 0:
        return True

    # If not divisible, it's not a Harshad number
    return False

Big(O) Analysis

Time Complexity

O(log n) – The input size is represented by the number n. Calculating the sum of digits involves iterating through each digit of the number. The number of digits in a number n is proportional to log n (base 10 or any other base). Therefore, calculating the digit sum takes O(log n) time. The divisibility check is a constant time operation, O(1). Therefore, the overall time complexity is dominated by the digit sum calculation, which is O(log n).

Space Complexity

O(1) – The algorithm calculates the digit sum and then performs a division. It uses a few integer variables to store the original number, the digit sum, and potentially a temporary variable during digit extraction. The number of these variables remains constant irrespective of the size of the input number N, where N is the input number. Therefore, the space complexity is constant.

Optimal Solution

Approach

The core idea is to figure out if a number is divisible by the sum of its digits. We simply need to find the sum of the digits of the input number and then check if the original number is divisible by this sum.

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

Take the input number.
Calculate the sum of its individual digits.
Check if the original number is perfectly divisible by the digit sum (meaning the remainder is zero).
If the remainder is zero, the number is a Harshad number; otherwise, it isn't.

Code Implementation

def is_harshad_number(number):
    number_string = str(number)
    digit_sum = 0

    # Calculate the sum of the digits
    for digit_char in number_string:
        digit_sum += int(digit_char)

    # Handle edge case to avoid division by zero
    if digit_sum == 0:
        return False

    # Check divisibility
    if number % digit_sum == 0:
        return True

    return False

Big(O) Analysis

Time Complexity

O(log n) – The primary operation is calculating the sum of the digits of the input number n. The number of digits in n is proportional to log n (base 10). We iterate through each digit to calculate their sum. Therefore, the time complexity is determined by the number of digits, making it O(log n).

Space Complexity

O(1) – The algorithm calculates the sum of the digits of the input number and checks for divisibility. It only uses a few integer variables to store the original number, the digit sum, and potentially a temporary variable for digit extraction. The number of these variables remains constant irrespective of the size of the input number N (where N represents the input number's value, not its digit count). Thus, the algorithm uses constant extra space.

Edge Cases

Case	How to Handle
Input is zero (n = 0)	Handle zero as a special case, returning true because technically it's divisible by zero, though may want to confirm this specific requirement with interviewer.
Input is a single-digit number (n < 10)	The sum of digits equals the number itself, hence it will always be divisible; return true.
Input is a very large number that may cause integer overflow when summing digits	Use a long data type to store the sum of digits to prevent integer overflow.
Input has many nines (e.g., 9999999)	This tests the efficiency of the digit summing, ensure it can handle a high number of digits without excessive computation.
Input where the digit sum is 1	Any number is divisible by 1, so should return true efficiently.
Maximum integer value (Integer.MAX_VALUE)	Test if the algorithm handles Integer.MAX_VALUE without overflowing during digit summation.
Negative Input	Problem specifies non-negative input, so either throw an exception or return false, clarifying desired behavior with the interviewer.
Number ends in zero but is not divisible	This tests that the sum is calculated correctly and the divisibility check is also correct.

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:

What is the expected range for the input integer n? Specifically, what is the maximum possible value of n?
Is zero considered a Harshad number? How should I handle the case when n is 0?
The problem states 'non-negative integer', so negative numbers are not valid inputs, correct?
Are we concerned about potential integer overflow issues when calculating the sum of digits?
Are there any specific performance expectations or limitations I should be aware of beyond standard optimization practices?

Brute Force Solution

Approach

The Harshad Number problem asks if a number is divisible by the sum of its digits. The brute force way is simply to calculate the digit sum and then check divisibility.

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

First, take the number you are given.
Next, find the sum of all its digits.
Finally, see if the original number can be divided evenly by the sum of its digits, with no remainder.

Code Implementation

def is_harshad_number(number_to_check):
    number_string = str(number_to_check)
    sum_of_digits = 0

    for digit_character in number_string:
        digit = int(digit_character)
        sum_of_digits += digit

    # Handle cases to avoid division by zero
    if sum_of_digits == 0:
        return False

    # Check if the number is divisible by the sum of its digits
    if number_to_check % sum_of_digits == 0:
        return True

    # If not divisible, it's not a Harshad number
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Take the input number.
Calculate the sum of its individual digits.
Check if the original number is perfectly divisible by the digit sum (meaning the remainder is zero).
If the remainder is zero, the number is a Harshad number; otherwise, it isn't.

Code Implementation

def is_harshad_number(number):
    number_string = str(number)
    digit_sum = 0

    # Calculate the sum of the digits
    for digit_char in number_string:
        digit_sum += int(digit_char)

    # Handle edge case to avoid division by zero
    if digit_sum == 0:
        return False

    # Check divisibility
    if number % digit_sum == 0:
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero (n = 0)	Handle zero as a special case, returning true because technically it's divisible by zero, though may want to confirm this specific requirement with interviewer.
Input is a single-digit number (n < 10)	The sum of digits equals the number itself, hence it will always be divisible; return true.
Input is a very large number that may cause integer overflow when summing digits	Use a long data type to store the sum of digits to prevent integer overflow.
Input has many nines (e.g., 9999999)	This tests the efficiency of the digit summing, ensure it can handle a high number of digits without excessive computation.
Input where the digit sum is 1	Any number is divisible by 1, so should return true efficiently.
Maximum integer value (Integer.MAX_VALUE)	Test if the algorithm handles Integer.MAX_VALUE without overflowing during digit summation.
Negative Input	Problem specifies non-negative input, so either throw an exception or return false, clarifying desired behavior with the interviewer.
Number ends in zero but is not divisible	This tests that the sum is calculated correctly and the divisibility check is also correct.