Check if product of first N natural numbers is divisible by their sum

0 0 7 minutes read

Given an integer N, the task is to check whether the product of first N natural numbers is divisible by the sum of first N natural numbers.
Examples:

Input: N = 3
Output: Yes
Product = 1 * 2 * 3 = 6
Sum = 1 + 2 + 3 = 6

Input: N = 6
Output: No

Naive Approach:

In this approach, we initialize the product and sum variables to 1 and 0 respectively. Then, we use a loop to calculate the product and sum of the first N natural numbers. Finally, we check if the product is divisible by the sum by using the modulo operator and return the result.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
 
// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
bool isDivisible(int n)
{
    int product = 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        product *= i;
        sum += i;
    }
    return (product % sum == 0);
}
 
 
// Driver code
int main()
{
    int n = 6;
    if (isDivisible(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
public class Main {
    // Function that return true if the product
    // of the first n natural numbers is divisible
    // by the sum of first n natural numbers
    public static boolean isDivisible(int n) {
        int product = 1, sum = 0;
        for (int i = 1; i <= n; i++) {
            product *= i;
            sum += i;
        }
        return (product % sum == 0);
    }
 
    // Driver code
    public static void main(String[] args) {
        int n = 6;
        if (isDivisible(n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Python3

# Python3 implementation of the approach
import math
 
# Function that return true if the product
# of the first n natural numbers is divisible
# by the sum of first n natural numbers
 
 
def isDivisible(n):
    product = 1
    sum = 0
    for i in range(1, n+1):
        product *= i
        sum += i
    return (product % sum == 0)
 
 
# Driver code
n = 6
if (isDivisible(n)):
    print("Yes")
else:
    print("No")

C#

using System;
 
class Program
{
 
  // Function that return true if the product
  // of the first n natural numbers is divisible
  // by the sum of first n natural numbers
  static bool IsDivisible(int n)
  {
    int product = 1, sum = 0;
    for (int i = 1; i <= n; i++)
    {
      product *= i;
      sum += i;
    }
    return (product % sum == 0);
  }
 
  // Driver code
  static void Main(string[] args)
  {
    int n = 6;
    if (IsDivisible(n))
      Console.WriteLine("Yes");
    else
      Console.WriteLine("No");
  }
}

Javascript

// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
function isDivisible(n) {
    let product = 1, sum = 0;
    for (let i = 1; i <= n; i++) {
        product *= i;
        sum += i;
    }
    return (product % sum === 0);
}
 
// Driver code
let n = 6;
if (isDivisible(n))
    console.log("Yes");
else
    console.log("No");

Output

No

Time Complexity: O(N)
Space Complexity: O(1)

Efficient Approach: We know that the sum and product of first N naturals are sum = (N * (N + 1)) / 2 and product = N! respectively. Now to check whether the product is divisible by the sum, we need to check if the remainder of the following equation is 0 or not.

N! / (N *(N + 1) / 2)
2 * (N – 1)! / N + 1
i.e. every factor of (N + 1) should be in (2 * (N – 1)!). So, if (N + 1) is a prime then we are sure that the product is not divisible by the sum.
So ultimately just check if (N + 1) is prime or not.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if n is prime
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
bool isDivisible(int n)
{
    if (isPrime(n + 1))
        return false;
    return true;
}
 
// Driver code
int main()
{
    int n = 6;
    if (isDivisible(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Function that returns true if n is prime
static boolean isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
static boolean isDivisible(int n)
{
    if (isPrime(n + 1))
        return false;
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 6;
    if (isDivisible(n))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by Code_Mech.

Python3

# Python 3 implementation of the approach
from math import sqrt
 
# Function that returns true if n is prime
def isPrime(n):
     
    # Corner cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True
 
    # This is checked so that we can skip
    # middle five numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return False
 
    for i in range(5, int(sqrt(n)) + 1, 6):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
 
    return True
 
# Function that return true if the product
# of the first n natural numbers is divisible
# by the sum of first n natural numbers
def isDivisible(n):
    if (isPrime(n + 1)):
        return False
    return True
 
# Driver code
if __name__ == '__main__':
    n = 6
    if (isDivisible(n)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function that returns true if n is prime
static bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
static bool isDivisible(int n)
{
    if (isPrime(n + 1))
        return false;
    return true;
}
 
// Driver code
static void Main()
{
    int n = 6;
    if (isDivisible(n))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
 
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP implementation of the approach
 
// Function that returns true if n is prime
function isPrime($n)
{
    // Corner cases
    if ($n <= 1)
        return false;
    if ($n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if ($n % 2 == 0 || $n % 3 == 0)
        return false;
 
    for ($i = 5; $i * $i <= $n; $i = $i + 6)
        if ($n % $i == 0 || $n % ($i + 2) == 0)
            return false;
 
    return true;
}
 
// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
function isDivisible($n)
{
    if (isPrime($n + 1))
        return false;
    return true;
}
 
// Driver code
$n = 6;
if (isDivisible($n))
    echo "Yes";
else
    echo "No";
 
// This code is contributed by Akanksha Rai
?>

Javascript

<script>
// javascript implementation of the approach
 
// Function that returns true if n is prime
function isPrime(n)
{
 
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function that return true if the product
// of the first n natural numbers is divisible
// by the sum of first n natural numbers
function isDivisible(n)
{
    if (isPrime(n + 1))
        return false;
    return true;
}
 
// Driver code
var n = 6;
if (isDivisible(n))
    document.write("Yes");
else
    document.write("No");
 
// This code is contributed by Princi Singh 
</script>

Output:

No

Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!