2. The following method of multiplying numbers was used in ancient times. Put the numbers to be multiplied side by side. Call them n1 and n2. If n1 is odd put an asterisk next to n2. Next, divide n1 by 2, discarding any remainder and multiply n2 by 2. If the new value of n1 is odd put an asterisk next to the new value of n2. Continue dividing n1 by 2 and discarding the remainder and doubling n2 until n1 is 0. Mark each value of n2 that is associated with an odd value of n1 with an asterisk. Then sum all the n2 values that have asterisks next to them. The result is the product of n1 * n2. Here is an example n1 n2 mark 17 25 * (because 17 is odd) 8 50 4 100 2 200 1 400 * (because 1 is odd) 0 Summing the n2s that are marked by an asterisk gives 425 which is 17*25. Reversing n1 and n2 gives the same result n1 n2 mark 25 17 * (because 25 is odd) 12 34 6 68 3 136 * (because 3 is odd) 1 272 * (because 1 is odd) 0 Note that 17 + 136 + 272 = 425 = 25*17 Notice that there is no provision for negative numbers in the above algorithm. Perhaps the omission was not important thousands of years ago but today we use negative numbers. Therefore your version of the algorithm should handle negative numbers. Specifically, n1 n2 result -17 25 -425 17 -25 -425 -17 -25 +425 Write a function named ancientMultiplication that implements this algorithm. Its signature is int ancientMultiplication(int n1, int n2) This function should return n1*n2 computed using the above algorithm modified to handle negative numbers.
-- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAEvz5E%3DY55JzPB%2B147cUYY0kUdDg8w%3Doah%3DjuBs_%2BVSauu_%2Bnw%40mail.gmail.com. For more options, visit https://groups.google.com/groups/opt_out.
