Good Number Or Not | Problem Code: ISGOODNM

help
1

A number N is called good if the sum of the factors of N, less than N, is equal to the number N. Given a number N, check if it is good or not. Print YES if it’s a good number, otherwise print NO .

Input:

  • First-line will contain the number N.

Output:

Print YES if N is good number, otherwise print NO.

Constraints

  • 1 ≤ N ≤ 1010

Sample Input 1:

6

Sample Output 1:

YES

Sample Input 2:

16

Sample Output 2:

NO

EXPLANATION:

  • In the first example, divisors of 6, less than 66 are 1,2,31,2,3, and (1+2+3)=6. Thus, 66 is a good number.
  • In the second example, 16 is not a good number as (1+2+4+8)=15.

My Solution:

#include <iostream>

using namespace std;

int main()
{
    int N, factorSum = 0;
    cin >> N;
    for (int i = 1; i < N; i++)
    {
        if (N % i == 0)
        {
            factorSum += i;
        }
    }

    if (N == factorSum)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}

I don’t know what I am doing wrong, please correct me.
Thanks!

1 Like
2

Despite posting for the first time, you formatted your code correctly. That’s cool.

Coming to the problem, the constraints mentioned:
1 \le N\le 10^{10}.

Will it fit in an Integer?

5 Likes
3

Yes, it is.
(6, 28)

4 
loop through sqrt(n) only i.e i*i<=N, 
because if(N%i == 0) then both (i,N/i) will be factor of N.
Also use long int.
2 Likes
5

I am newbie here, please elaborate your point little more.:sweat_smile:

6

Um, made some changes to your code.

The Code 
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    long long int N, factorSum = 0;
    cin >> N;
    
    for (int i = 1; i <= sqrt(N); i++)
    {
        if(N % i == 0)
        {
            factorSum += i;
            
            // If i divides N,
            // then (N/i) will also divide N
            
            if(i != 1) {
                factorSum += N / i;
            }
        }
    }

    if (N == factorSum)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}
2 Likes
7

I think you have doubt regarding why sqrt is the upper limit?
Link has excellent explanation for the same.

Why square root as the upper limit?

sqrt(x) * sqrt(x) = x. So if the two factors are the same, they're both the square root. 
If you make one factor bigger, you have to make the other factor smaller. 
This means that one of the two will always be less than or equal to sqrt(x), 
so you only have to search up to that point to find one of the two matching factors.
You can then use x / fac1 to get fac2.
1 Like
8

Thanks! @sudo_s :pray: for helping me. I never imagine to put square root as the upper limit.

1 Like
9

Thanks a lot @suman_18733097 :pray: for helping me.
Two things I learn from you, first is to help community and second is to write comments in the code. :star_struck: