Codingame Solution: Egyptian multiplication
Goal
You have to multiply two integers (a&b) by means of a method used in Ancien Egypt, described in Rhind’s hieratic papyrus written circa −1650 by Ahmes. This method is still used in Russia.First, sort the two numbers.
Then follow the steps below, the algorithm uses base-2 decomposition of the biggest number.
We multiply 12 by 5, here is what you have to print, excepted the comments after hashes.
12 * 5
= 12 * 4 + 12 # Divide 5 by 2, the remain is 1 and 5=2×2+1, thus 12*5=12*(2*2+1)=12*2*2+12=24*2+12
= 24 * 2 + 12 # Divide 2 by 2, 2=1*2+0 and 12*5=24*(1*2+0)+12=48*1+12
= 48 * 1 + 12 # Divide 1 by 2, 1=0*2+1 and 12*5=48*(0*2+1)+12=12+48
= 48 * 0 + 12 + 48 # End of the algorithm
= 60
Input
Two integers separated by a space.
Output
The description of the successive operations.
Constraints
0<= a, b <= 32768
Solution
When we observe the output, the first line is simply the sorted input printed out, separated by a multiplication sign. After that intermediate steps are printed in the form of a times b and the already found summands. These intermediate steps have two different formats. When b is odd it is printed with an additional a summand and if it is even, only a and b get doubled or halved. When we modify a and b in every iteration, we need two printing lines and additional zero-checks. Or we use only the main loop as zero check. This way the whole algorithm can be implemented pretty short:
a, b = gets.split.map(&:to_i) if a < b a, b = b, a end puts "#{a} * #{b}" r = "" s = 0 while b > 0 if b.odd? r+= " + #{a}" s+= a b-= 1 else a*= 2 b/= 2 end puts "= #{a} * #{b}#{r}" end puts "= #{s}"