Day 19: HackerRank 30 Days Of Code Solution | Interfaces

Day 19 of HackerRank's 30 Days of Code is about interfaces. The coding part is small: write a class that implements a given interface and returns the sum of a number's divisors. The real lesson is the idea behind it. An interface is a contract. It says "any class that signs this must provide these methods", and code that uses the interface does not care which class is behind it.

This is a topic that comes up in almost every Java interview, usually as "abstract class vs interface". Solving this problem carefully, and understanding why the locked code prints the interface name, gives you a concrete example to talk about.

Problem

HackerRank gives you an interface called AdvancedArithmetic with one method, int divisorSum(int n). You have to write a class Calculator that implements this interface. Its divisorSum must return the sum of every positive number that divides n with no remainder, including 1 and n itself.

Input: one integer n.

Output: you do not print anything yourself. The locked main method prints I implemented: AdvancedArithmetic on the first line and the value returned by your method on the second.

Constraints: 1 ≤ n ≤ 1000.

Input:
6

Output:
I implemented: AdvancedArithmetic
12

The divisors of 6 are 1, 2, 3 and 6, and 1 + 2 + 3 + 6 = 12.

Approach

There are two separate things to get right: the Java structure and the maths.

The structure. Declare class Calculator implements AdvancedArithmetic. Because the interface method is implicitly public, your method must also be public. If you leave the modifier out, the compiler complains that you are trying to give weaker access. The locked code creates the object as AdvancedArithmetic myCalculator = new Calculator();. The variable's type is the interface, which is exactly how interfaces are used in real code: you program against the contract, not the class.

The first output line comes from myCalculator.getClass().getInterfaces()[0].getName(). That uses reflection to ask "what is the first interface this object's class implements?". So the line only prints correctly if Calculator really implements AdvancedArithmetic.

The maths. The simple way is to try every i from 1 to n and add i when n % i == 0. With n at most 1000 that is fine. A better habit is to notice that divisors come in pairs. If i divides n, then n / i also divides n. One of each pair is at most √n, so you only need to loop i from 1 while i * i <= n and add both i and n / i.

The one trap: for a perfect square like 16, the pair (4, 4) would add 4 twice. So add the partner only when it is different from i.

Dry run with n = 6: i = 1 divides 6, add 1 and 6 (sum 7). i = 2 divides 6, add 2 and 3 (sum 12). i = 3 gives 9 > 6, so stop. Sum is 12.

Solution in Java

import java.util.Scanner;

interface AdvancedArithmetic {
    int divisorSum(int n);
}

class Calculator implements AdvancedArithmetic {
    // Divisors come in pairs (i, n / i), so we only need to loop up to sqrt(n)
    public int divisorSum(int n) {
        int sum = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                sum += i;               // the small divisor
                int partner = n / i;
                if (partner != i) {     // avoid adding sqrt(n) twice for perfect squares
                    sum += partner;     // the matching big divisor
                }
            }
        }
        return sum;
    }
}

class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.close();

        AdvancedArithmetic myCalculator = new Calculator();
        int sum = myCalculator.divisorSum(n);
        System.out.println("I implemented: " + myCalculator.getClass().getInterfaces()[0].getName());
        System.out.println(sum);
    }
}

On HackerRank, the interface and the Solution class are already there. You only write the Calculator class. The old solution on this page used the full 1 to n loop, which is correct. I switched to the pair loop because it scales much better and is what an interviewer would hope to see.

I ran it on the sample and on these cases, and cross-checked against the simple loop for every n from 1 to 1000:

• n = 1 gives 1 (1 is its own only divisor).
• n = 7 gives 8 (a prime: 1 + 7).
• n = 16 gives 31 (1 + 2 + 4 + 8 + 16, with 4 counted once).
• n = 1000 gives 2340.

Output

I implemented: AdvancedArithmetic
12

Complexity

Time: O(√n) with the pair loop, compared with O(n) for checking every number.

Space: O(1).

Common mistakes

• Forgetting public on divisorSum. Interface methods are public by default, and an implementation cannot reduce that.
• Adding the square root twice for perfect squares when using the pair loop.
• Stopping the simple loop at n / 2 and forgetting to add n itself. The problem counts n as a divisor.
• Making Calculator extend the interface, or trying to write new AdvancedArithmetic(). A class implements an interface, and you cannot create an object of an interface directly.

If abstract classes still feel fuzzy, read Day 13: Abstract Classes next to this one, then try the OOP MCQs on abstract classes and interfaces.

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