number of ‘4’ + number of ‘7’ = k (given constant)

How to maximize number of ‘4’ and minimize number of ‘7’ such that :

number of ‘4’ is divisible by 7 &

number of ‘7’ is divisble by 4

Could you please give an efficient algorithm for this?

number of ‘4’ + number of ‘7’ = k (given constant)

How to maximize number of ‘4’ and minimize number of ‘7’ such that :

number of ‘4’ is divisible by 7 &

number of ‘7’ is divisble by 4

Could you please give an efficient algorithm for this?

1 Like

This is a problem on diophantine equation. Observe a beautiful pattern:-

7%4=3

14%4=2

21%4=1

28%4=0

35%4=3 and so on.

So, of all the numbers of the form (28x+7)%4=3, (28x+14)%4=2, (28x+21)%4=1 and 28x%4=0 for all non-negative integers x.

If k%4 is 0, then find the largest integer lesser or equal to k which is of the form 28x.

If k%4 is 1, then find the largest integer lesser or equal to k which is of the form (28x+21).

If k%4 is 2, then find the largest integer lesser or equal to k which is of the form (28x+14).

If k%4 is 3, then find the largest integer lesser or equal to k which is of the form (28x+7).

Hence you get the maximum number of 4’s, and on subtracting this number from k, you will get the minimum number of 7’s.

A sample implementation of the code : http://ideone.com/rwW4Rw

2 Likes