Find whether n! is divisible by sum of first n natural integers or not in C++

Given an integer value n. Product of first n natural integers or n! (factorial of n )is denoted by P  and the sum of first n consecutive natural integers is denoted by S. If S is a factor of P, then print YES, otherwise print NO.

Example

n=1, p=1, s=1 –> P is divisible by S so, YES

n=2, p=1*2=2 , s=1+2=3 –>P is not divisible by S so, NO

n=3, p=1*2*3=6, s=1+2+3 –>P is divisible by S so, YES

n=4, p=1*2*3*4=24, s=1+2+3+4=10 –>P is not divisible by S so, NO

Wrong approach

If you think you can simply calculate S and P and check if S divides P or not, then think a little more about calculating n! for large values. You will get integer overflow if you try to calculate P i.e., n! for a large value of n.

---

Right approach

We know from mathematics that formula for calculating  sum of first n consecutive natural integers is:

S = ( n * (n+1) )/2

P = n! = 1*2*3*4*………..*(n-1)*n.

After dividing P by S;

P/s = (1*2* …….. *(n-1)*n) / (( n * (n+1) )/2)

Then canceling out n from numerator and denominator ;

P/S =  (1*2* …….. *(n-1)) / ((n+1)/2)

Now we can carefully analyze denominator (n+1)/2;

• We can easily see that if n is an odd integer then n+1 is obviously an even integer. If n+1 is even then it will be easily canceled out by 2 in its denominator and it will be reduced to a value that is between 1 and n-1 so, we can easily cancel them out from numerator and denominator both, and hence P will be divisible by S. So our first conclusion can be drawn from here that whenever n is odd then P is divisible by S.

Example for  n=5 ;  P/S = (1*2*3*4*5)/((5*(5+1))/2)

P/S = (1*2*3*4)/(6/2)

P/S = (1*2*3*4)/3

P/S =  1*2*4 =  8

• Let’s consider the case now when n is even, n+1 will obviously be odd. There can be 2 possibilities when n+1 is odd;

1. When  n+1 is an odd prime integer, then it is never possible to cancel out n+1 in the denominator because the maximum value of integer present in the numerator is n-1. So, the second conclusion can be drawn from here that whenever n is even and n+1 is odd prime then P is not divisible by S.
2. The second possibility of n being even is that when n+1 is an odd composite. In this case, there must be some odd factor of n+1 present in the numerator within range 3 to n-1, so eventually, n+1 will get canceled out from the denominator. So, we can draw our third conclusion from this case that whenever n is even and n+1 is odd composite then P is divisible by S.

Example for n being even and n+1 being odd prime ;

n = 6  –> n+1=7  here n+1 is odd prime so, P/S = (1*2*3*4*5*6)/((6*7)/2)

P/S = (1*2*3*4*5*2)/7

we can easily observe that 7 in the denominator will never get canceled out, so P is not divisible by S.

Example for n being even and n+1 being odd composite ;

n = 8  –> n+1=9  here n+1 is odd composite so, P/S = (1*2*3*4*5*6*7*8)/((8*9)/2)

P/S = (1*2*3*4*5*6*7*2)/9

P/S = 1*2*4*5*2*7*2 = 1120

so P is not divisible by S.

---

Now let’s code all of these conclusions in C++.

#include<bits/stdc++.h>
using namespace std;

string solve(int n)
{
    string ans="NO";
    if(n%2)
    {
        ans="YES";
    }
    else
    {
        long long int i=2;
        for(;i*i<=n+1; i++)
        {
            if((n+1)%i==0)
            {
                ans="YES";
                break;
            }
        }
    }
    return ans;
}
int main()
{
    int n; 
    cin>>n;
    cout<<solve(n);
    return 0;
}

 

      If you think that this article has added any value to your algorithmic knowledge, then please share your valuable feedback in the comment section. Thank you!