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