In this problem ([192A Funky Numbers](https://mirror.codeforces.com/contest/192/problem/A)), given an integer 'n', find if it can be the sum of two triangular numbers where a triangular number equals k(k+1)/2 for some positive integer k.
I have two questions regarding this problem.
In many solutions I saw, people would increment and int i from i to Math.sqrt(n) and use this value to find the k value for the second triangular number by using the equation n — (i(i+1)/2). Why stop at Math.sqrt(n)?
Following the above algorithm, k2 (the k of the second triangular number) could be found as such:
int k2 = (int)(Math.sqrt((n — (i*(i+1)/2)) * 2));
This time, why is Math.sqrt() used, and why is the result multiplied by 2?
Thank you for your help, Codeforces community.
1- n<=1e9 so if you go over sqrt(n) (which is nearly 3e4) ,consider i=1e5 which is greater than the sqrt then the (i)th triangular number will be((i*(i+1))/2)=1e10 which is greater than n, so you only need to iterate to sqrt n.
2-you want to check if there is sum of two triangular numbers is equal to n, so consider we have k1,k2. (k1*(k1+1))/2 + (k2*(k2+1))/2 = n . we get k1 by iterate for all numbers <= sqrt(n) ((brute force)) and for each k1 we have : (k2*(k2+1))/2 = ( n — (k1*(k1+1))/2 ) now you can easily see that : k2*(k2+1) = ( n — (k1*(k1+1))/2 ) * 2 (this is why we multiply by 2. then also you can see that : k2 < sqrt( ( n — (k1*(k1+1))/2 ) * 2 ) < (k2+1) while [sqrt( ( n — (k1*(k1+1))/2 ) * 2 )] is a real number not an integer, so : (int) ( sqrt( ( n — (k1*(k1+1))/2 ) * 2 )) will give you k2. now you just need to check if : (k1*(k1+1))/2 + (k2*(k2+1))/2 = n then print yes if not continue with k1+1 and so on till sqrt(n)
hope this help you :)
Thank you so much, your explanation is extremely clear :)
<3