Amazon Interview Question
Write a function to return the minimum number of squares whose sum equals to given positive integer. For example, for 17, the answer is 2 as it can be expressed as 1 + 16. For 12, it's not 4 due to 9 + 1 + 1 + 1; instead it is 3 due to 4 + 4 + 4.
Interview Answer
Anonymous
Sep 1, 2017
You can find lots of solutions for this problem online. I implemented a simple recursive function which seemed to work correctly in the first attempt. def minimum_num_of_sum_of_squares(n): result = n for i in range(n, 0, -1): is_square = ((i ** .5) % 1) == 0 if is_square: result = min(result, 1 + minimum_num_of_sum_of_squares(n - i)) return result