Finding "decent" numbers algorithm reasoning?

Question

Problem

Sherlock Holmes is getting paranoid about Professor Moriarty, his archenemy. All his efforts to subdue Moriarty have been in vain. These days Sherlock is working on a problem with Dr. Watson. Watson mentioned that the CIA has been facing weird problems with their supercomputer, 'The Beast', recently.

This afternoon, Sherlock received a note from Moriarty, saying that he has infected 'The Beast' with a virus. Moreover, the note had the number N printed on it. After doing some calculations, Sherlock figured out that the key to remove the virus is the largest 'Decent' Number having N digits.

A 'Decent' Number has -

• 3 or 5 or both as its digits.
• No other digit is allowed.
• Number of times 3 appears is divisible by 5.
• Number of times 5 appears is divisible by 3.

Meanwhile, the counter to destruction of 'The Beast' is running very fast. Can you save 'The Beast', and find the key before Sherlock?

Input Format The 1st line will contain an integer T, the number of test cases. This is followed by T lines, each containing an integer N i.e. the number of digits in the number

Output Format Largest Decent number having N digits. If no such number exists, tell Sherlock that he is wrong and print '-1'

Constraints 1<=T<=20 1<=N<=100000

Sample Input

4
1
3
5
11

Sample Output

-1
555
33333
55555533333

Explanation For N=1, there is no such number.

For N=3, 555 is only possible number.

For N=5, 33333 is only possible number.

For N=11, 55555533333 and all of permutations of digits are valid numbers, among them, the given number is the largest one.

Answer

for _ in range(int(input())):
    n = int(input())
    c = 5*(2*n%3)
    if c > n:
        print(-1)
    else:
        print('5' * (n-c) + '3'*c)

Question

Can someone explain the reasoning behind it? Specifically what the assignment for the 'c' variable is doing?

Source: https://www.hackerrank.com/challenges/sherlock-and-the-beast

Answer 1

A mathematical solution:

Let a = len of the '5's, b = len of the '3's. So

a + b = N

We know that 3 divides a, and 5 divides b, so let a = 3n, b = 5m

3n+5m = N

This is a diophantine equation (http://en.wikipedia.org/wiki/Diophantine_equation) with one solution being (n0, m0) = (2N, -N), and general solution

(n,m) = (5k+2N, 3K-N), k any integer

The problem now is to minimize the quantity 3k-N (because you want MORE '5's), so that 3k-N > 0. This is the same as finding the k for which 3k is the next multiple of 3 FROM N.

For example, if N = 10 or 11, we are looking for 3k = 12, or k = 4.

3k-N is therefore the distance between N and this next multiple of 3. The author of the solution claims that 3k-N = 2N%3 , and you prove this by exhaustion, evaluating the case for which N%3 = 0, 1, and 2. For the record, the '2' in the expression '2N%3' isn't unique, it would work for any number of the sequence 2, 5, 8, 11..., and why the author chose this particular expression, I cannot say.

You can also think about how N%3 in this sense is how close N is to the next LOWER multiple of 3.