3099. Harshad Number

Problem Description

An integer is considered a Harshad number if it is divisible by the sum of its digits. You are provided with an integer x. Your task is to return the sum of the digits of x if x is a Harshad number. If x is not a Harshad number, return -1.

Intuition

To determine if an integer x is a Harshad number, we need to compute the sum of its digits. We can achieve this by iteratively taking the last digit of x using the modulo operation with 10, and then reduce x by removing the last digit using integer division by 10. Sum these digits as you extract them.

Once we have the sum of the digits, denoted as s, we check if x is divisible by s using the modulus operator. If x % s equals 0, x is a Harshad number, and we return the sum s. If not, we return -1 since x does not satisfy the Harshad number condition. This approach is straightforward and efficient due to the simplicity of manipulating the digits of the number using basic arithmetic operations.

Learn more about Math patterns.

Solution Approach

To implement the solution for determining whether a number x is a Harshad number, we can use a simulation approach, as follows:

Initialize two variables s to 0 and y to x. Here, s will store the sum of the digits, and y is a copy of x that we will manipulate to extract each digit.
Use a while loop to iterate while y is greater than 0. Inside the loop:
- Calculate the last digit of y using y % 10 and add it to s.
- Remove the last digit from y using integer division (y //= 10) to proceed to the next digit in the next iteration.
After summing all the digits, check if x is divisible by s using the modulus operation (x % s == 0):
- If the condition holds true, x is a Harshad number, so return the sum s.
- Otherwise, return -1 as x is not a Harshad number.

The algorithm efficiently examines all digits of x using simple arithmetic operations. The flow ensures that the sum of the digits is computed and then checks the divisor condition to validate the Harshad number property.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example with x = 18 to illustrate the solution approach for determining if it is a Harshad number.

Initialize Variables:
- Start with s = 0 to store the sum of digits.
- Copy x to y, so y = 18.
Iterate to Sum Digits:
- First Iteration:
  - Calculate the last digit of y using y % 10, which is 18 % 10 = 8.
  - Add this digit to s, so s = 0 + 8 = 8.
  - Remove the last digit from y using integer division y //= 10, making y = 18 // 10 = 1.
- Second Iteration:
  - Calculate the last digit of y using y % 10, which is 1 % 10 = 1.
  - Add this digit to s, so s = 8 + 1 = 9.
  - Remove the last digit from y using integer division y //= 10, making y = 1 // 10 = 0.
- The loop ends as y is now 0.
Check Harshad Condition:
- With all digits summed, s = 9.
- Check if x is divisible by s using x % s == 0, which is 18 % 9 == 0.
- Since the condition is true, 18 is a Harshad number.
Return Result:
- As 18 is a Harshad number, return the sum of its digits s = 9.

This example demonstrates how the algorithm efficiently calculates the sum of digits and checks the divisibility condition to verify the Harshad number property.

Solution Implementation

1class Solution:
2    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
3        """
4        Calculate the sum of the digits of a number and check if the number
5        is a Harshad Number (also known as a Niven number). Returns the digit sum
6        if the input number is a Harshad Number, otherwise, return -1.
7
8        A Harshad Number is an integer that is divisible by the sum of its digits.
9        """
10        digit_sum = 0  # Initialize sum of digits
11        temp = x  # Keep a copy of the input number for processing
12      
13        # Calculate the sum of the digits
14        while temp > 0:
15            digit_sum += temp % 10  # Add the last digit to the sum
16            temp //= 10  # Remove the last digit
17      
18        # Check if the number is divisible by the sum of its digits
19        if x % digit_sum == 0:
20            return digit_sum  # Return the sum of digits if it is a Harshad Number
21        else:
22            return -1  # Return -1 if it is not a Harshad Number
23

1class Solution {
2    public int sumOfTheDigitsOfHarshadNumber(int x) {
3        int sumOfDigits = 0; // Initialize a variable to store the sum of digits
4        for (int temp = x; temp > 0; temp /= 10) {
5            sumOfDigits += temp % 10; // Add the last digit of temp to sumOfDigits
6        }
7        // Check if x is a Harshad number, if yes return the sum of digits, otherwise return -1
8        return x % sumOfDigits == 0 ? sumOfDigits : -1;
9    }
10}
11

1class Solution {
2public:
3    // Function to calculate the sum of digits of a Harshad number
4    int sumOfTheDigitsOfHarshadNumber(int x) {
5        int sum = 0; // Initialize sum of digits to zero
6
7        // Loop to calculate sum of digits of x
8        for (int y = x; y > 0; y /= 10) {
9            sum += y % 10; // Add the last digit to sum
10        }
11
12        // If x is divisible by the sum of its digits, return the sum
13        return (x % sum == 0) ? sum : -1; // Return -1 if it is not a Harshad number
14    }
15};
16

1// Function to calculate the sum of the digits of x and check if x is a Harshad number
2function sumOfTheDigitsOfHarshadNumber(x: number): number {
3    // Initialize sum of digits
4    let sumOfDigits = 0;
5
6    // Temporary variable y to iterate over each digit of x
7    for (let y = x; y !== 0; y = Math.floor(y / 10)) {
8        // Add the last digit of y to sumOfDigits
9        sumOfDigits += y % 10;
10    }
11  
12    // If x is divisible by the sum of its digits, return the sum
13    // Otherwise, return -1 indicating x is not a Harshad number
14    return x % sumOfDigits === 0 ? sumOfDigits : -1;
15}
16

Time and Space Complexity

The time complexity of the code is O(\log x). This is because the loop iterates over the digits of x, and the number of digits d in x is O(\log x) when expressed in base 10.

The space complexity of the code is O(1). This is due to the usage of a fixed number of variables (s and y) and no additional data structures that scale with input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know