algoadvance

Leetcode 3099. Harshad Number

Problem Statement

Given a positive integer x, determine whether it is a Harshad number (also known as a Niven number). A Harshad number is an integer that is divisible by the sum of its digits. Implement a function in C++ that returns true if the given number x is a Harshad number, and false otherwise.

Example:

• Input: 18
• Output: true
  • Explanation: 18 is a Harshad number because the sum of its digits is 1 + 8 = 9, and 18 is divisible by 9.
• Input: 19
• Output: false
  • Explanation: 19 is not a Harshad number because the sum of its digits is 1 + 9 = 10, and 19 is not divisible by 10.

Clarifying Questions

1. Range of Input: Is there a specific range for the input integer x?
   • Assumption: The integer x will be positive and within the typical range for standard integer operations in C++.
2. Output Format: Should the function return a boolean value or a string ("true" or "false")?
   • Assumption: The function should return a boolean value.

Strategy

1. Calculate Sum of Digits: Extract each digit of the given integer x and compute the sum of its digits.
2. Check Divisibility: Check if x is divisible by the sum of its digits.
3. Return Result: Return true if x is divisible by the sum of its digits, otherwise return false.

Code

Here is the implementation of the above strategy in C++:

#include <iostream>

bool isHarshadNumber(int x) {
    int sumOfDigits = 0;
    int originalNumber = x;
    
    // Calculate sum of digits
    while (x > 0) {
        sumOfDigits += x % 10;
        x /= 10;
    }
    
    // Check if the number is divisible by the sum of its digits
    return (originalNumber % sumOfDigits == 0);
}

int main() {
    int number = 18;
    std::cout << (isHarshadNumber(number) ? "true" : "false") << std::endl;
    number = 19;
    std::cout << (isHarshadNumber(number) ? "true" : "false") << std::endl;
    return 0;
}

Time Complexity

• Time Complexity: The main computation involves extracting the digits of the number x, which takes O(log10(x)) time because we are repeatedly dividing the number by 10.
• Space Complexity: The space complexity is O(1) since we are using a constant amount of extra space for variables.

This code efficiently determines whether a given number is a Harshad number by leveraging basic arithmetic operations and digit extraction.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?