Skip to content

Latest commit

 

History

History
77 lines (54 loc) · 2.33 KB

013.md

File metadata and controls

77 lines (54 loc) · 2.33 KB

2520. Count the Digits That Divide a Number

Difficulty: 🟢 Easy

Given an integer num, return the number of digits in num that divide num.

An integer val divides nums if nums % val == 0.

Examples:

Example 1:

Input: num = 7
Output: 1
Explanation: 7 divides itself, hence the answer is 1.

Example 2:

Input: num = 121
Output: 2
Explanation: 121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2.

Example 3:

Input: num = 1248
Output: 4
Explanation: 1248 is divisible by all of its digits, hence the answer is 4.

Constraints:

  • 1 <= num <= 109
  • num does not contain 0 as one of its digits.

Solutions

O(log n) solution

Python3

class Solution:
    def countDigits(self, num: int) -> int:
        original, total = num, 0
        while num:
            n = num % 10
            total += 0 if original % n else 1
            num //= 10
        return total

The given solution solves the problem by performing the following steps:

  1. Initialize original as num and total as 0.
  2. Iterate through each digit of num by dividing num by 10 in each iteration until num becomes 0.
    • Get the current digit n by taking num % 10.
    • Check if original % n == 0.
      • If true, increment total by 1.
      • If false, continue to the next iteration.
    • Divide num by 10 to move to the next digit.
  3. After the loop ends, return the value of total as the count of digits in num that divide num.

Complexity Analysis

The time complexity of this algorithm is O(log num) because we iterate through each digit of num.

The space complexity of the algorithm is O(1) because we only use a constant amount of space to store the variables original, total, and n.

Summary

The given solution counts the number of digits in num that divide num. It iterates through each digit of num and checks if the digit divides num. It maintains a count of such digits and returns the count at the end. The algorithm has a time complexity of O(log num) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.