Find Digits | HackerRank Solution | Problem Solving Algorithms

Find Digits looks like a warm-up, and it is one. But it checks two habits that you will use in a lot of harder problems: pulling a number apart digit by digit with % 10 and / 10, and guarding against division by zero before you divide. Many people get the second part wrong on their first submission.

It is also a nice reminder that you sometimes need to keep a copy of your input. The loop that extracts digits destroys the number, but the divisibility test needs the original value. If you mix the two up, the code compiles fine and gives wrong answers.

Problem

You are given a positive integer n. Look at each digit of n one at a time and check whether that digit divides n with no remainder. Count how many digits pass the test.

Two details matter. First, every occurrence counts separately, so for 111 the digit 1 divides 111 three times and the answer is 3. Second, a 0 digit can never count, because dividing by zero is not defined.

Input format: the first line has t, the number of test cases. Each of the next t lines has one integer n.

Output format: for each test case, print the count on its own line.

Constraints: on HackerRank, 1 <= t <= 15 and 0 < n < 10^9, so n fits comfortably in an int.

Input
2
12
1012

Output
2
3

For 12, both 1 and 2 divide 12. For 1012, the two 1s and the 2 divide 1012, while the 0 is skipped, which gives 3.

Approach

You do not need strings here. Plain arithmetic is enough and it is faster to write.

1. Save the original number in a separate variable, say original.
2. While n is greater than 0, take the last digit with n % 10.
3. If the digit is not 0 and original % digit == 0, add one to the count.
4. Remove the last digit with n = n / 10 and repeat.

The order of the checks inside the if matters. Java evaluates && left to right and stops as soon as one side is false. Writing digit != 0 first means the modulo never runs when the digit is 0, so you never hit an ArithmeticException.

Dry run for n = 1012:

• digit 2: 1012 % 2 = 0, count = 1, n becomes 101
• digit 1: 1012 % 1 = 0, count = 2, n becomes 10
• digit 0: skipped, n becomes 1
• digit 1: 1012 % 1 = 0, count = 3, n becomes 0 and the loop ends

The digits come out from right to left, but since we only count them, the order does not matter.

Solution in Java

The old version on this page used HackerRank's template that writes to a file named by the OUTPUT_PATH environment variable. That works on the site but throws an error when you run it on your own machine. This version reads from standard input and prints to standard output, so you can test it anywhere. The logic is the same.

import java.util.Scanner;

public class Solution {

    // Counts how many digits of n divide n exactly.
    static int findDigits(int n) {
        int original = n;   // keep a copy, because we destroy n below
        int count = 0;
        while (n > 0) {
            int digit = n % 10;          // last digit
            if (digit != 0 && original % digit == 0) {
                count++;                 // every occurrence counts
            }
            n /= 10;                     // drop the last digit
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            int n = sc.nextInt();
            out.append(findDigits(n)).append('\n');
        }
        System.out.print(out);
    }
}

I also ran it on a few cases of my own: 111 gives 3 (repeated digits count), 10 gives 1 (only the 1, the 0 is skipped), 999999999 gives 9, and 105 gives 2 (1 and 5 divide 105).

Output

2
3

Complexity

Time: O(d) per test case, where d is the number of digits. Since n is below 10^9, d is at most 9, so each test case is effectively constant time.

Space: O(1). We only keep a few integer variables.

Common mistakes

• Checking against the shrinking number. If you write n % digit instead of original % digit, you test the digit against what is left of n, not the real number. For 1012 that gives wrong results after the first step.
• Putting the zero check second. original % digit == 0 && digit != 0 crashes on any number containing 0, because the modulo runs before the check.
• Counting distinct digits only. Using a Set to store digits looks clean but gives 1 for 111 instead of 3. The problem wants every occurrence.
• Using a string when you then parse each character. It works, but Character.getNumericValue calls and conversions add noise. The arithmetic loop is shorter and is the pattern interviewers expect.

Related: Day 25: Running Time and Complexity uses the same divisibility idea to test for primes.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice