java - Sherlock and The beast - issue

Question

Question: Sherlock Holmes is getting paranoid about Professor Moriarty, his arch-enemy. All his efforts to subdue Moriarty have been in vain. These days Sherlock is working on a problem with Dr. Watson. Watson mentioned that the CIA has been facing weird problems with their supercomputer, 'The Beast', recently.

This afternoon, Sherlock received a note from Moriarty, saying that he has infected 'The Beast' with a virus. Moreover, the note had the number N printed on it. After doing some calculations, Sherlock figured out that the key to remove the virus is the largest Decent Number having N digits.

A Decent Number has the following properties:

• 3, 5, or both as its digits. No other digit is allowed.
• Number of times 3 appears is divisible by 5.
• Number of times 5 appears is divisible by 3.

Meanwhile, the counter to the destruction of 'The Beast' is running very fast. Can you save 'The Beast', and find the key before Sherlock?

I am trying to solve "Sherlock and the beast" problem (above) in hackerrank and here is what I ended with -

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    for(int i=0;i<n;i++) {
        int subject = s.nextInt();
        if(isPerfectlyDivisible(subject, 3)) {
            System.out.println(stringBuilder("5", subject));
            continue;
        }

        if (isPerfectlyDivisible(subject, 5)) {
            System.out.println(stringBuilder("3", subject));
            continue;
        }

        if(!isPerfectlyDivisible(subject, 5) && !(isPerfectlyDivisible(subject, 3))) {
            List<Integer> multipliers = dividedMultipliers(subject);
            if (multipliers.isEmpty()) {
                System.out.println("-1");
            } else {
                System.out.println(stringBuilder("5", multipliers.get(0))+stringBuilder("3", multipliers.get(1)));
            }
        }
    }
}

private static boolean isPerfectlyDivisible(int n, int divider) {
    if (n < divider) return false;
    if (n%divider == 0) return true;
    return false;
}

private static List<Integer> dividedMultipliers(int n) {
    List<Integer> multipliers = new ArrayList<Integer>();
    for(int i=n;i>0;i--) {  
      if( (i%3 == 0) && ((n-i)%5 == 0)) {
          multipliers.add(i);
          multipliers.add(n-i);
          break;
      }    
    }
    return multipliers;
}

private static String stringBuilder(String s, int times) {
    StringBuffer buffer = new StringBuffer();
    for(int i=0;i<times;i++) {
        buffer.append(s);
    }
    return buffer.toString();
}

}

There were test cases failing for this. I tried looking at one of the failing test cases whose input is

5
2194
12002
21965
55140
57634

Surprisingly for 21965 the output is all 5's whereas my code above returns all 3's..which seems to be the expected output..Not sure where the issue? Any insights would be helpful

Answer 1

You are looking for the largest decent number, so you should maximise the number of 5s. For example, 21965 is divisible by 5, but the largest 21965-digit decent number is not one that consists of 3s only; it is one that has 21960 5s and 5 3s.

Your dividedMultipliers routine already goes for the most 5s, but treating a number that is divisible by 5 as special undermines that logic; it will create the least optimum decent number.

Get rid of that special case. (You could also get rid of the other special case which checks against a number consisting of only 5s, because dividedMultipliers handles that case immediately in the first iteration.)