Why this code is not working?

general
1

Gay and Prime

Send Feedback

Jitender defines a number “super gay”, if it is gay as well as prime.

Jitender defines a number “gay”, if its recursive sum of squares of its digits is 1.

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.

Going by this definition, you have to predict whether the given number is “super gay” or not.

The answer is in boolean i.e. either Yes or No. So, you have to answer all test cases correctly to get full marks. There is no partial marking.

Note: Please note that for the purposes of this problem, 1 is not prime.

Input format

The first line of input contains a single integer P, (1≤P≤10000), which is the number of queries that follow. Each queries should be processed identically and independently.

Each query consists of a single line of input. It contains candidate, m, (1≤m≤10000).

Output format

For each query there is a single line of output. The single output line consists of YES or NO, indicating whether m is a “super gay”.

Sample Test Cases:

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;
}

    }

}

2

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
3

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)…