Given an integer N, representing objects placed adjacent to each other, the task is to count the number of ways to remove objects such that after their removal, exactly M objects are left and the distance between each adjacent object is equal.
Examples:
Input: N = 5, M = 3
Output: 4
Explanation:
Let the initial arrangement be A1 A2 A3 A4 A5.
The following arrangements are possible:
- A1 A2 A3 _ _
- _ A2 A3 A4 _
- _ _ A3 A4 A5
- A1_ A3_ A5
Therefore, the total count of possible arrangements is 4.
Input: N = 2, M = 1
Output: 2
Approach: The idea is based on the observation that an arrangement of M objects with D adjacent spaces takes (M + (M – 1) * D) length, say L. For this arrangement, there are (N – L + 1) options. Therefore, the idea is to iterate over D from 0 till L ? N and find the number of ways accordingly.
Follow the steps below to solve the problem:
- If the value of M is 1, then the number of possible arrangements is N. Therefore, print the value of N.
- Otherwise, perform the following steps:
- Initialize two variables, say ans to 0, to store the total number of required arrangements.
- Iterate a loop using a variable D. Perform the following steps:
- Store the total length required for the current value of D in a variable, say L as M + (M – 1) * D.
- If the value of L is greater than N, then break out of the loop.
- Otherwise, update the number of arrangements by adding the value (N – L + 1) to the variable ans.
- After completing the above steps, print the value of ans as the total number of arrangements.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of ways of// removing objects such that after removal,// exactly M equidistant objects remainvoid waysToRemove(int n, int m){ // Store the resultant // number of arrangements int ans = 0; // Base Case: When only // 1 object is left if (m == 1) { // Print the result and return cout << n; return; } // Iterate until len <= n and increment // the distance in each iteration for (int d = 0; d >= 0; d++) { // Total length if adjacent // objects are d distance apart int len = m + (m - 1) * d; // If len > n if (len > n) break; // Update the number of ways ans += (n - len) + 1; } // Print the result cout << ans;}// Driver Codeint main(){ int N = 5, M = 3; waysToRemove(N, M); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to count the number of ways of// removing objects such that after removal,// exactly M equidistant objects remainstatic void waysToRemove(int n, int m){ // Store the resultant // number of arrangements int ans = 0; // Base Case: When only // 1 object is left if (m == 1) { // Print the result and return System.out.println(n); return; } // Iterate until len <= n and increment // the distance in each iteration for(int d = 0; d >= 0; d++) { // Total length if adjacent // objects are d distance apart int len = m + (m - 1) * d; // If len > n if (len > n) break; // Update the number of ways ans += (n - len) + 1; } // Print the result System.out.println(ans);}// Driver Codepublic static void main(String[] args){ int N = 5, M = 3; waysToRemove(N, M);}}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach# Function to count the number of ways of# removing objects such that after removal,# exactly M equidistant objects remaindef waysToRemove(n, m): # Store the resultant # number of arrangements ans = 0 # Base Case: When only # 1 object is left if (m == 1): # Print the result and return print(n) return d = 0 # Iterate until len <= n and increment # the distance in each iteration while d >= 0: # Total length if adjacent # objects are d distance apart length = m + (m - 1) * d # If length > n if (length > n): break # Update the number of ways ans += (n - length) + 1 d += 1 # Print the result print(ans)# Driver Codeif __name__ == "__main__" : N = 5 M = 3 waysToRemove(N, M)# This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the number of ways of// removing objects such that after removal,// exactly M equidistant objects remainstatic void waysToRemove(int n, int m){ // Store the resultant // number of arrangements int ans = 0; // Base Case: When only // 1 object is left if (m == 1) { // Print the result and return Console.Write(n); return; } // Iterate until len <= n and increment // the distance in each iteration for(int d = 0; d >= 0; d++) { // Total length if adjacent // objects are d distance apart int len = m + (m - 1) * d; // If len > n if (len > n) break; // Update the number of ways ans += (n - len) + 1; } // Print the result Console.Write(ans);}// Driver codestatic void Main(){ int N = 5, M = 3; waysToRemove(N, M);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript program for the above approach// Function to count the number of ways of// removing objects such that after removal,// exactly M equidistant objects remainfunction waysToRemove( n, m){ // Store the resultant // number of arrangements var ans = 0; // Base Case: When only // 1 object is left if (m == 1) { // Print the result and return document.write( n); return; } // Iterate until len <= n and increment // the distance in each iteration for (var d = 0; d >= 0; d++) { // Total length if adjacent // objects are d distance apart var len = m + (m - 1) * d; // If len > n if (len > n) break; // Update the number of ways ans += (n - len) + 1; } // Print the result document.write( ans);}// Driver Codevar N = 5, M = 3;waysToRemove(N, M);</script> |
Output:
4
Time Complexity: O(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
