g0c00l.g33k - 1 year ago 70

Java 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`

Answer Source

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.)