# Why this code is not working?

Gay and Prime

Send Feedback

#### For Example: 7

``````7 = 7*7= 49
49 = 4*4 + 9*9 = 97
97= 9*9 + 7*7= 130
130= 1*1+3*3+0*0=10
10= 1*1+0*0=1
Hence, 7 is gay number.
``````

#### Sample Input 1:

``````4
1
7
383
1000
``````

#### Sample Output 1:

``````NO
YES
YES
NO
``````

my solution:
#include<bits/stdc++.h>
using namespace std;
int gay(int n)
{
int sum=0;
while(n!=0)
{
int a;
a=n%10;
sum+=a*a;
n=n/10;
}
if(sum>=9)
{
gay(sum);
}
if(sum==1)
{
return 1;
}
else
{
return 0;
}
}
int is_prime(int n)
{
if(n==1)
{
return 0;
}
else
{

int i,c=0;
for(int i=2;i<=n/2;i++)
{
if(n%i==0)
{
c++;
}
}
if(c==0)
{
return 1;}
else
{
return 0;
}
}
}
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a=0,b=0,c=0;
a=n;
b=gay(n);
c=is_prime(a);
// cout<<b<<endl<<c<<endl;*/
if(b==1&&c==1)
{
cout<<“YES”<<endl;
}
else
{
cout<<“NO”<<endl;
}

``````    }
``````

}

You should indent your code. It helps in understanding. Also Instead of naively checking whether a number is prime or not every time you should store which numbers are prime in that given range => Sieve of Eratosthenes. Most importantly there’s a problem with your recursive sum function.

``````int gay(int n){
cout << n << endl;
int sum=0;
while(n!=0){
int a;
a=n%10;
sum+=a*a;
n=n/10;
}

if(sum>=9)
gay(sum);  # sum = gay(sum)

if(sum==1)
return 1;
else
return 0;
# return sum;
}

``````

I guess this should do it. Not sure about the time complexity-part though.

``````int gay(int n){
int sum=0;
while(n!=0){
int a;
a=n%10;
sum+=a*a;
n=n/10;
}

if(sum>=9)
sum = gay(sum);

return sum;
}

``````
1 Like

your code will fail for n=2111

2111 = 2* 2 + 1* 1 +1* 1 + 1 *1= 7
7 = 7 * 7= 49
49 = 4 * 4 + 9 * 9 = 97
97= 9 * 9 + 7 * 7= 130
130= 1 * 1 + 3 * 3 + 0 * 0=10
10= 1 * 1 + 0 * 0=1
this number is super gay…but your ‘gay’ function will return false in first step
just change a little bit in your function ‘gay’ for AC i.e. if(sum==1||sum==7) return 1;

you may get TLE because time complexity of your solution is O(Pm)…just make it O(Psqrt(m)) by changing for loop limit in function is_prime from n/2 to sqrt(n)…