We need to calculate all the answers for all Ns before processing the input. First of all we need to find all the Pythagorean triplets where the sum of that triplet is less than 3000. At worst case, we need to look all the numbers up to 3000. if we have a^2+b^2=c^2, we need to take all the possible pairs a,b and check if the sum of their squares is a full square. Meanwhile, we need to keep an answer array ( we will call it ANS), where ANS[I] shows the answer for the number I. When taking all the triplets, we check for one thing if a+b+c<= 3000, if it is then we need to update the ANS[a+b+c] value. After doing all these, we just need to input the number N and output ANS[N].
No comments:
Post a Comment