9
\$\begingroup\$

The problem in question is a coding challenge from Hackerrank:

Problem Statement

You are given an integer N. Find the digits in this number that exactly divide N (division that leaves 0 as remainder) and display their count. For N=24, there are 2 digits (2 & 4). Both of these digits exactly divide 24. So our answer is 2.

Note

If the same number is repeated twice at different positions, it should be counted twice, e.g., For N=122, 2 divides 122 exactly and occurs at ones' and tens' position. So for this case, our answer is 3. Division by 0 is undefined. Input Format

The first line contains T (the number of test cases), followed by T lines (each containing an integer N).

Constraints
1≤T≤15
0 < N <10 ^ 10

Output Format

For each test case, display the count of digits in N that exactly divide N in a separate line.

Here's my code:

package algorithms.Warmup;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by user1 on 4/2/15.
 */
public class FindDigitsTest {

    static Scanner sc = new Scanner(System.in);

    private static Long[] findDigits(long num) {

        ArrayList<Long> digits = new ArrayList<>();

        //extract all digits from input number and store in arraylist
        while (num > 0) {

            long quotient = num / 10;
            long remainder = num - (quotient * 10);
            num = quotient;
            digits.add(remainder);

        }

        Long[] result = new Long[digits.size()];
        result = digits.toArray(result) ;
        return result;

    }

    private static int findCount(Long[] list, long num) {

        int count = 0;
        for(int i = 0; i < list.length; i++) {

            //ignore division by zero- DON'T FORGET!!!
            if(list[i] == 0) {
                continue;
            }
            if (num % list[i] == 0){
                count++;
            }
        }

        return count;

    }
    public static void main(String[] args) {

        ArrayList<Integer> al = new ArrayList<>();

        //read in number of test cases
        System.out.println("Enter number of test cases: ");
        int T = sc.nextInt();

        //loop through number of test cases
        for(int i = 0; i < T; i++) {

            System.out.println("Enter the number: ");
            long N = sc.nextLong();

            //extract digits of number and store in array
            Long[] nDigits = findDigits(N);

            //calculate num. of digits which exactly divide N
            int answer = findCount(nDigits, N);

            //store answer in final arraylist
            al.add(answer);

        }

        //loop through final arraylist to print answers
        for(int i = 0; i < al.size(); i++) {
            System.out.println(al.get(i));
        }


    }
}

Even though the submission is correct, and the output is as desired, I feel there are many ways this can be improved, I just don't know how. I see that I have too many ArrayLists and Arrays here and there throughout the code, maybe that can be replaced to begin with.

I'm not completely proficient in Java yet, so my knowledge of Java APIs and Collections is still somewhat limited. That might be one reason for the inefficient code.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review. Very nice first question. \$\endgroup\$ – RubberDuck Apr 2 '15 at 20:53
  • \$\begingroup\$ remainder = num % 10; \$\endgroup\$ – spyr03 Aug 25 '15 at 13:02
5
\$\begingroup\$

I see that I have too many ArrayLists and Arrays here and there throughout the code, maybe that can be replaced to begin with.

Yes, that would probably be a good idea. In findDigits you internally use an ArrayList, I'm guessing because it's a lot easier to use than an array (which is true, a List is the correct collection type here). But then you transform it to an array, which isn't really needed.

Returning lists instead of arrays is perfectly acceptable in Java, and is in fact used in most cases (an exception might be made for fixed length arrays in performance critical code, eg coordinates).

So just change your signature from Long[] findDigits(long num) to List<Long> findDigits(long num), and then use a List in findCount as well.

Misc

  • declare variables in as small a scope as possible. sc isn't really needed anywhere except in main, so declare it there.
  • don't use short variables names. sc would be clearer as scanner and al could be results.
  • findDigits could be getDigits, after all you are not really searching for the digits or computing them (they are right there), just getting them.
  • findCount could be countDivisors, and then num could be divisor.
  • the question says that you are given an integer, but you use long instead.
  • your while loop in findDigits could be simplified to digits.add(num % 10); num = num / 10;.
\$\endgroup\$
  • \$\begingroup\$ Thanks for your detailed answer, Tim! I have not yet read up on Lists, so wasn't able to use List specifically for this problem. But I did read up on Lists vs ArrayLists before writing my solution, and according to the answer on this SO problem, it says- When you define your list as: List myList = new ArrayList(); you can only call methods and reference members that belong to List class. If you define it as: ArrayList myList = new ArrayList(); \$\endgroup\$ – Manish Giri Apr 3 '15 at 1:27
  • \$\begingroup\$ you'll be able to invoke ArrayList specific methods and use ArrayList specific members in addition to those inherited from List. This is why I thought that maybe using ArrayList would give me access to use List methods too along with the ones from ArrayList. After reading your suggestions, I looked at the comments below the answer and realized that List is an interface and it's methods are basically ArrayList methods for both cases. I feel now the answer was somewhat misleading. Thanks for all your pointers. Also, the constraint says about range of N: 0 < N < 10 ^10. That's why i used long. \$\endgroup\$ – Manish Giri Apr 3 '15 at 1:29
4
\$\begingroup\$

I have reviewed your code and here are my analysis-

use modulo operator(%) to get the remainder in place of using too much mathematics like

long remainder = num - (quotient * 10); //note: it will just shorten your code 
// but will be overhead as well because internally it will 
//perform three operation(multiplication, subtraction, division).
// C = A % B is equivalent to C = A – B * (A / B).

could be simplified to

long remainder = num % 10;

You don't need an extra method to count divisor it can be done in the same method itself.

You can merge both method while extracting the digit itself can check whether it's a divisor or not?

static int findDigits(int n) {
    int count = 0;
    int num = n;
    while (n > 0) {
        int r = n % 10;  // to get the remainder
        if (r != 0 && num % r == 0)  // checking for the divisor
            count++;
        n = n / 10;   // using to remove last digit
    }
    return count;
}

Note: if still need more explanation about the code then click here.

\$\endgroup\$
  • \$\begingroup\$ Any comments on the performance of % compared to the simpler subtraction? \$\endgroup\$ – Toby Speight Mar 25 at 9:12
  • \$\begingroup\$ I just google and find this article -embeddedgurus.com/stack-overflow/2011/02/… which mentioned that modulo is slower than subtraction because it performs division + subtraction in between to calculate the same. that C = A % B is equivalent to C = A – B * (A / B) In that case i feel simpler abstraction is having good performance over modulo. \$\endgroup\$ – Kanahaiya Mar 25 at 13:45
  • \$\begingroup\$ Sorry, I meant that you might want to edit the answer with that information, rather than comment. It's a good idea to present the alternatives and justify your preference if you can. \$\endgroup\$ – Toby Speight Mar 25 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.