AngryPanda - 1 year ago 47

Java Question

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`

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.