AngryPanda - 2 years ago 73
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();
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++)
for(int k = 0;k < 5*j;k++)
break;
}
}
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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download