Number of ways to divide a N elements equally into group of at least 2

0 0 3 minutes read

Given an integer N denoting the number of elements, the task is to find the number of ways to divide these elements equally into groups such that each group has at least 2 elements.

Examples:

Input: N = 2
Output: 1
Explanation: There can be only one group.

Input: N = 10
Output: 3
Explanation: There are 3 ways to divide elements:
One group having all the 10 elements.
Two groups where each group has 5 elements.
Five groups where each group has 2 elements.

Approach: The above problem can be solved using the below-given brute force approach. In every iteration of the loop, i represents the number of groups. If N is completely divisible by i, hence, the elements can be equally divided among groups. Follow the steps below to solve the problem:

Declare variable ways and initialize it by 0.
Iterate over the range [1, N/2] using the variable i and perform the following tasks:
- Check if N is completely divisible by i.
- If yes, then increment ways by 1.
After performing the above steps, print the value of ways as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the given approach
#include <iostream>
using namespace std;
 
// Function to find the number of ways
int numberofWays(int N)
{
    // Variable to store the number of ways
    int ways = 0;
    int i;
 
    // Loop to find total number of ways
    for (i = 1; i <= N / 2; i++) {
        if (N % i == 0)
            ways++;
    }
 
    // Returning the number of ways
    return ways;
}
 
// Driver Code
int main()
{
 
    // Declaring and initialising N
    int N = 10;
 
    // Function call
    int ans = numberofWays(N);
 
    // Displaying the answer on screen
    cout << ans;
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the number of ways
  static int numberofWays(int N)
  {
    // Variable to store the number of ways
    int ways = 0;
    int i;
 
    // Loop to find total number of ways
    for (i = 1; i <= N / 2; i++) {
      if (N % i == 0)
        ways++;
    }
 
    // Returning the number of ways
    return ways;
  }
 
  public static void main (String[] args)
  {
 
    // Declaring and initialising N
    int N = 10;
 
    // Function call
    int ans = numberofWays(N);
 
    // Displaying the answer on screen
    System.out.print(ans);
  }
}
 
// This code is contributed by hrithikgarg03188

Python3

# Python code for the above approach 
 
# Function to find the number of ways
def numberofWays(N):
 
    # Variable to store the number of ways
    ways = 0;
    i = None
 
    # Loop to find total number of ways
    for i in range(1, (N // 2) + 1):
        if (N % i == 0):
            ways += 1
 
    # Returning the number of ways
    return ways;
 
# Driver Code
 
# Declaring and initialising N
N = 10;
 
# Function call
ans = numberofWays(N);
 
# Displaying the answer on screen
print(ans);
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
 
class GFG {
 
  // Function to find the number of ways
  static int numberofWays(int N)
  {
    // Variable to store the number of ways
    int ways = 0;
    int i;
 
    // Loop to find total number of ways
    for (i = 1; i <= N / 2; i++) {
      if (N % i == 0)
        ways++;
    }
 
    // Returning the number of ways
    return ways;
  }
 
  public static void Main(string[] args)
  {
 
    // Declaring and initialising N
    int N = 10;
 
    // Function call
    int ans = numberofWays(N);
 
    // Displaying the answer on screen
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript code for the above approach 
 
        // Function to find the number of ways
        function numberofWays(N)
        {
         
            // Variable to store the number of ways
            let ways = 0;
            let i;
 
            // Loop to find total number of ways
            for (i = 1; i <= Math.floor(N / 2); i++) {
                if (N % i == 0)
                    ways++;
            }
 
            // Returning the number of ways
            return ways;
        }
 
        // Driver Code
 
        // Declaring and initialising N
        let N = 10;
 
        // Function call
        let ans = numberofWays(N);
 
        // Displaying the answer on screen
        document.write(ans);
 
  // This code is contributed by Potta Lokesh
    </script>

Output

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!