Hackerrank - Sherlock and the Beast

Question

I am trying to solve the Sherlock and The Beast HackerRank challenge. Most tests timeout, however when I try a custom stretch test case (T = 20 and all N = 100000), it returns successfully, so I'm not sure what the problem is.

The idea of the algorithm is that I find the number of possible combinations of threes and fives for a given number of digits, then I treat threes as zeros and fives as ones, in order to process a binary number. So for N = 3 digits, we have 8 combinations (from 7 to 0) which in binary terms is (descending) from 111 to 000, which in three and five terms is from 555 to 333.

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int testCases = in.nextInt();
        for(int i = 0; i < testCases; i++){
            System.out.println( solve( in.nextInt() ) );
        }
    }

    private static String solve(int n){


        long combos = (long)Math.pow(2,n);               
        for(long i = combos-1; i>=0; i--){          
            String toStr = String.format("%"+n+"s", Long.toBinaryString(i)).replace(' ', '0');

            String modified = toStr.replace("0","3").replace("1","5");
            int threes =0;          
            for( int j=0; j<modified.length(); j++ ) {
                if( modified.charAt(j) == '3' ) {
                    threes++;
                } 
            }                  
            if(threes%5==0) {
                int fives =0;          
                for( int k=0; k<modified.length(); k++ ) {
                    if( modified.charAt(k) == '5' ) {
                        fives++;
                    } 
                }  
                if(fives%3==0) return modified;
            }               
        }
        return "-1";
    }
}

Answer 1

My non-exhaustive list of comments, considering that you seem to prefer (based on observed skill level) plain Java and do not want to use Java 8 yet.

1. Adhere to the Java's coding standards. One of the catches here is that method names are in camelCase, so it would be private static String solve(int n) {.

2. Intendation and code formatting. You seem to not be using a single standard for all your code. Furthermore I have to say that using spaces where neccessary will not cause any harm, some examples and improvements.

   2.1. for(int i = 0; i < t; i++){ -> for (int i = 0; i < t; i++) {

   2.2. long combos = (long)Math.pow(2,n); -> long combos = (long)Math.pow(2, n);

   2.3. if(threes%5==0) { -> if (threes % 5 == 0) {

   Please be consistent with your formatting is the bottom line.

3. On to the next point, variable names. It does not hurt to use longer variable names if that makes them more meaningful. In your main you have a variable called t, this name is not descriptive, please consider describing what it actually means. Another example is i, ii and iii in your for-loops, it is much more natural to use i, j, k for these variables.

4. You could use more abstraction, as your solve method is not easy to follow at all. Consider creating smaller methods that process one step at a time, this will also enable you to be able to test your methods at some point.