Question Name:Charsi in Love

#include <stdio.h>
#include<math.h>
int binarySearch(int low,int high,int key)
{
    while(low<=high)
    {
        int mid=(low+high)/2;
        int x = (mid*(mid+1));
        if(x<key)
        {
            low=mid+1;
        }
        else if(x>key)
        {
            high=mid-1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
 
int main()
{
    int n,i,j,b;
    int flag=0;
    scanf("%d",&n);
    for(i=1;i<=sqrt(n);i++){
        b = n - ((i*(i+1))/2);
        int y = binarySearch(1,sqrt(2*b),2*b);
        if(y>0) {
            flag =1;
            break;
        }
    }
    if(flag==1)
    printf("YES");
    else
    printf("NO");
    return 0;
}

Problem Description

Its been a few days since Charsi is acting weird. And finally you(his best friend) came to know that its because his proposal has been rejected.

He is trying hard to solve this problem but because of the rejection thing he can’t really focus. Can you help him? The question is: Given a number n , find if n can be represented as the sum of 2 desperate numbers (not necessarily different) , where desperate numbers are those which can be written in the form of (a*(a+1))/2 where a > 0 .

Input :

The first input line contains an integer n (1<=n<=10^9).

Output :

Print “YES” (without the quotes), if n can be represented as a sum of two desperate numbers, otherwise print “NO” (without the quotes).

  • Test Case 1

    Input (stdin)

    45
    

    Expected Output

    NO
  • Test Case 2

    Input (stdin)

    256
    

    Expected Output

    YES

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.