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;
- 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.
- 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!
Leave a Reply