1

I was solving the following question on HackerRank. Unable to proceed ahead, I googled this question and found this code:

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
          int t = in.nextInt();
         while((t--)>0){
             int n = in.nextInt();
             StringBuffer answer = new StringBuffer();
            for(int j = 0;j <= n/5;j++){
                //System.out.println("J="+j+" N/5="+(n/5));
                //System.out.println("(n-5*j) = "+(n-5*j));
                 if((n-5*j)%3 == 0){
                    for(int k = 0;k< n-5*j;k++)
                         answer.append("5");
                     for(int k = 0;k < 5*j;k++)
                         answer.append("3");
                    System.out.println(answer.toString());
                     break;
                 }
            }
             if(answer.toString().equals(""))
                 System.out.println(-1);
         }
    }
}

I am having difficulty understanding how this code works; especially the (n-5*j)%3 part. Could someone help me understand it step by step? Thanks.

AngryPanda
  • 1,261
  • 2
  • 19
  • 42

2 Answers2

4

To solve this problem, we need to find a and b such that:

- a + b = n
- a is divisible by 5 (a = 5*j where j is some integer)
- b is divisible by 3, (b = n-a = n-5*j is divisible by 3, written as (n-5*j)%3 == 0

The answer would be: (b times)5 followed by (a times)3

What we need is to find j, such that n = 5*j + 3*something.

If we dont find any such j, the problem has no solution.

If there are many solutions, the best one is the one that gives the highest b, because it has more fives on the left. But, highest b means lowest j. Therefore, we start checking for j from 0 upward,

  for(int j = 0;j <= n/5;j++) // j cannot be > n/5, of course

As soon as we find j that verifies the requirements, we're done because it must the best one (lowest j). Does j provide a solution? Well let us check for this:

   if((n-5*j)%3 == 0) // if so, then j is a solution: b=n-5*j and a=5*j

    for(int k = 0;k< n-5*j;k++)
        answer.append("5"); // print 5 b times
    for(int k = 0;k < 5*j;k++)
        answer.append("3"); // print 3 a times

The rest of the code is for parsing the input and solving for many values of n, I dont think it needs explanation.

A.S.H
  • 29,101
  • 5
  • 23
  • 50
1
Scanner in = new Scanner(System.in);
int t = in.nextInt();

This code right here is pretty self explanatory. It creates the new scanner and reads an integer input.

while((t--)>0){
         int n = in.nextInt();
         StringBuffer answer = new StringBuffer();

The -- in the while loop says "Hey, if I subtract one from t, will it still be greater than zero? If so, keep going!" -- means subtract one, similar to how ++ means plus one. The int n simply takes another scanner input and the StringBufferis what is used to create the final solution output by adding onto it whatever we want. If you know what a StringBuilder is, it is similar to that. Difference between StringBuilder and StringBuffer explains the difference well.

for(int j = 0;j <= n/5;j++){

This for loop runs on the condition 'j <= n/5'. If j is less than or equal to (<=) the integer n divided by 5, then it will run the code in the loop. The j++ on the end simply increments the integer j, which was declared as zero when the loop first ran, by one. This is so that it does not always evaluate as true and create an infinite loop, since those are bad.

if((n-5*j)%3 == 0){

This if statement performs the operation '(n-5*j)%3' then compares if the result is equal to zero, if so it runs the code. Because of the order of operations, the expression in the parenthesis will evaluate first. 'n-5*j' also follows the order of operations, so it does not evaluate how one may originally think. It multiplies the integer j times 5, then subtracts the product from n. The % on the end means divide the first number by the following number, then return the remainder. So, 3%3 would return 0, since 3 divides evenly into 3. 62%3 would return 2, since 3 goes into 60 evenly and the last two are the remainder.

for(int k = 0;k< n-5*j;k++)
    answer.append("5");
for(int k = 0;k < 5*j;k++)
    answer.append("3");

These two for loops here are very similar, so I am just going to explain the first one of them and you should be able to interpret the other. Similar to the other for loops (the basic for loops at least, enhanced for loops are different), the for loop defines the variable k and sets it to zero right at the start. It does not create the k variable every iteration.

Also, you may be saying, "How can you have two k variables in the same class?" This is because the k variable is defined in an enclosing scope, which means only the code inside the loop can access the k variable. So, outside of the loop you could declare in again if you want (which the author did).

The expression 'k< n-5*j' is almost identical to the expression I explained above, just without a %. After evaluating and running if the condition is met, it increases k one time and runs the code in the loops, then reevaluates.

'answer.append("5");' appends '5' to the answer StringBuffer. It does not append it as and integer, it appends as a string/character. It will add this onto the end of the string, regardless of the length of the StringBuffer.

System.out.println(answer.toString());
break;

This will print out the current value of the answer StringBuilder. Note that to print it out, you must use the .toString() method. The StringBuilder objects is NOT a string, it must be converted to a string before it can be used as one. After printing it breaks out of the closest loop it runs in, so it would break out of:

for(int j = 0;j <= n/5;j++){}

To the last bit:

if(answer.toString().equals(""))
             System.out.println(-1);

This converts the answer stringbuilder to a string (as mentioned above), the checks if it is empty (nothing would have been appended since StringBuilders are empty by default) and only runs the println if it IS.

Community
  • 1
  • 1
Inaudible Jive
  • 139
  • 2
  • 8