4
\$\begingroup\$

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";
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You say that you're testing this with n=100000? It quite clearly can't give correct results for any value of n greater than 63, so I think you need to start by checking your test wrapper. \$\endgroup\$ – Peter Taylor Apr 16 '14 at 16:09
  • \$\begingroup\$ Strange thing is that I didn't test it locally, I just relied on Hackerrank's interface which indeed returned "success" for n=100000. I ca see now that the algorithm is off. Anyway thanks. \$\endgroup\$ – millenseed Apr 17 '14 at 15:45
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Fixed, thanks. Though I wasn't following standards and best practices in the online editor of hackerrank, plus the code's wrapper + function defs were provided by them. Hence the non-use of Java 8. \$\endgroup\$ – millenseed Apr 17 '14 at 10:36

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.