We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The key to solve this problem is to properly process multiple of primes. It should be done in reverse order so that for given prime we only take into account those multiples that have only preceeding prime factors and don't have next prime factors. For example for 7 we would have: 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 84 and 98. There is no multiple of 11 and 13. For each prime multiples we calculate all possible sums. In processing those sums we backtrack if the current sum is less then 0 or we can't get rid of this prime in the fraction.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #152: Writing 1/2 as a sum of inverse squares
You are viewing a single comment's thread. Return to all comments →
The key to solve this problem is to properly process multiple of primes. It should be done in reverse order so that for given prime we only take into account those multiples that have only preceeding prime factors and don't have next prime factors. For example for 7 we would have: 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 84 and 98. There is no multiple of 11 and 13. For each prime multiples we calculate all possible sums. In processing those sums we backtrack if the current sum is less then 0 or we can't get rid of this prime in the fraction.