AngryPanda AngryPanda - 7 months ago 27
Java Question

Sherlock and The Beast

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.

Answer

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.

Comments