"Sherlock and the Beast" challenge in Java

Question

I have been trying to solve the following problem on hackerrank.com, but when I submit the code it shows unsuccessful submission due to timeout. Can anyone help me out?

Sherlock and the Beast

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class test {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int t = in.nextInt();
    int a[] = new int[t];


    // reading test cases

    for( int i=0; i<t; i++){
        a[i] = in.nextInt();
    }       

    int n = 0;  // length of decent string


    boolean break1 ; // for breaking 2 for loops after getting the output for each test case

    for( int i=0; i<t; i++){
        n = a[i];
        int testx = n/3;
        int testy = n/5;
        break1 = false;

        for( int x = testx; x >= 0; x--){

            for( int y = testy; y >= 0; y--){

                if( ( x==0 && y== 0 ) ){

                    System.out.println("-1");

                    break1 = true;                      
                    break;
                }

                else if ( n % (3*x+5*y) == 0){                                          

                    System.out.println( getdecentString(x, y) );

                    break1 = true;
                    break;

                }                                   

            }

            if ( break1 == true)
                break;

        }       
    }



}   


// function to generate decentString

static String getdecentString(int x, int y){  
    String decentString = "";
    x = 3*x;
    y = 5*y;

    for( int j=1; j <= x; j++)
        decentString =  decentString + "5";

    for( int k=1; k <= y; k++)
        decentString =  decentString + "3"; 

    return decentString;

}       


}

Answer 1

As Robert pointed out, your code spends a lot of time in getdecentString. A faster way to generate Strings would be to use the StringBuilder class, e.g.:

StringBuilder decentString = new StringBuilder();
...
for ( int j = 1; j <= x; j++ )
{
    decentString.append( "5" );
}
...
return decentString.toString();

Answer 2

When you need to break out of nested loops, there are two things you can do. First, you can move the second loop into a different method and return a value signalling to break out of the first loop. An example would be moving the following into a method that returns a boolean.

for( int y = testy; y >= 0; y--){

    if( ( x==0 && y== 0 ) ){

        System.out.println("-1");

        break1 = true;                      
        break;
    }

    else if ( n % (3*x+5*y) == 0){                                          

        System.out.println( getdecentString(x, y) );

        break1 = true;
        break;

    }                                   

}

Replace the breaks with return true; and put a return false; at the end. Now, you can replace this (and the entire innermost-loop):

if ( break1 == true)
    break;

With:

if (newMethod(param1, param2, ...) {
    break;
}

This is the recommended option, but another option is to use a labelled loop and break out of the label, like the following:

outerLoopLabel:
for (...) {

    for (...) {

        if (condition) {
            break outerLoopLabel;
        }
    }
}

This will break out of both loops without the need for messy conditional checking. (Check this post on Stack Overflow.)