Given two integers N and K, the task is to check whether N can be represented as sum of K distinct positive integers.
Examples:
Input: N = 12, K = 4
Output: Yes
N = 1 + 2 + 4 + 5 = 12 (12 as sum of 4 distinct integers)Input: N = 8, K = 4
Output: No
Approach: Consider the series 1 + 2 + 3 + … + K which has exactly K distinct integers with minimum possible sum i.e. Sum = (K * (K – 1)) / 2. Now, if N < Sum then it is not possible to represent N as the sum of K distinct positive integers but if N ≥ Sum then any integer say X ≥ 0 can be added to Sum to generate the sum equal to N i.e. 1 + 2 + 3 + … + (K – 1) + (K + X) ensuring that there are exactly K distinct positive integers.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function that returns true if n// can be represented as the sum of// exactly k distinct positive integersbool solve(int n, int k){ // If n can be represented as // 1 + 2 + 3 + ... + (k - 1) + (k + x) if (n >= (k * (k + 1)) / 2) { return true; } return false;}// Driver codeint main(){ int n = 12, k = 4; if (solve(n, k)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function that returns true if n // can be represented as the sum of // exactly k distinct positive integers static boolean solve(int n, int k) { // If n can be represented as // 1 + 2 + 3 + ... + (k - 1) + (k + x) if (n >= (k * (k + 1)) / 2) { return true; } return false; } // Driver code public static void main(String[] args) { int n = 12, k = 4; if (solve(n, k)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by anuj_67.. |
Python3
# Python 3 implementation of the approach# Function that returns true if n# can be represented as the sum of# exactly k distinct positive integersdef solve(n,k): # If n can be represented as # 1 + 2 + 3 + ... + (k - 1) + (k + x) if (n >= (k * (k + 1)) // 2): return True return False# Driver codeif __name__ == '__main__': n = 12 k = 4 if (solve(n, k)): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{ // Function that returns true if n // can be represented as the sum of // exactly k distinct positive integers static bool solve(int n, int k) { // If n can be represented as // 1 + 2 + 3 + ... + (k - 1) + (k + x) if (n >= (k * (k + 1)) / 2) { return true; } return false; } // Driver code static public void Main () { int n = 12, k = 4; if (solve(n, k)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by ajit. |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if n// can be represented as the sum of// exactly k distinct positive integersfunction solve(n, k){ // If n can be represented as // 1 + 2 + 3 + ... + (k - 1) + (k + x) if (n >= (k * (k + 1)) / 2) { return true; } return false;}// Driver codevar n = 12, k = 4;if (solve(n, k)) document.write("Yes");else document.write("No");// This code is contributed by todaysgaurav</script> |
PHP
<?php// PHP implementation of the approach// Function that returns true if n// can be represented as the sum of// exactly k distinct positive integersfunction solve($n, $k){ // If n can be represented as // 1 + 2 + 3 + ... + (k - 1) + (k + x) if ($n >= ($k * ($k + 1)) / 2) { return true; } return false;}// Driver code$n = 12;$k = 4;if (solve($n, $k)) echo "Yes";else echo "No";// This code is contributed by ihritik?> |
Output
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach 2: Dynamic Programming:
Here’s the dynamic programming (DP) approach to solve the same problem:
- Define a 2D array dp of size (n+1) x (k+1).
- Initialize dp[i][j] to false if either i is 0 or j is 0, and to true if j is 1.
- For i from 1 to n and j from 2 to k, do the following steps:
- a. If i >= j, then set dp[i][j] to dp[i-1][j] || dp[i-j][j-1].
- b. If i < j, then set dp[i][j] to dp[i-1][j].
- If dp[n][k] is true, return true, else return false.
- Here’s the C++ code for the above DP approach:
C++
#include <iostream>#include <vector>using namespace std;bool canSumToDistinctIntegers(int n, int k) { vector<vector<bool>> dp(n+1, vector<bool>(k+1, false)); for (int i = 0; i <= n; i++) { dp[i][0] = false; } for (int j = 0; j <= k; j++) { dp[0][j] = false; } for (int j = 1; j <= k; j++) { dp[1][j] = true; } for (int i = 1; i <= n; i++) { for (int j = 2; j <= k; j++) { if (i >= j) { dp[i][j] = dp[i-1][j] || dp[i-j][j-1]; } else { dp[i][j] = dp[i-1][j]; } } } return dp[n][k];}int main() { int n = 12, k = 4; if (canSumToDistinctIntegers(n, k)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
public class GFG { public static boolean canSumToDistinctIntegers(int n, int k) { // Create a 2D DP array to store the results of subproblems boolean[][] dp = new boolean[n + 1][k + 1]; // Initialize base cases for (int i = 0; i <= n; i++) { dp[i][0] = false; } for (int j = 0; j <= k; j++) { dp[0][j] = false; } for (int j = 1; j <= k; j++) { dp[1][j] = true; } // Fill the DP array bottom-up for (int i = 1; i <= n; i++) { for (int j = 2; j <= k; j++) { if (i >= j) { dp[i][j] = dp[i - 1][j] || dp[i - j][j - 1]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][k]; } public static void main(String[] args) { int n = 12, k = 4; // Check if it is possible to form a sum of k distinct integers if (canSumToDistinctIntegers(n, k)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
def can_sum_to_distinct_integers(n, k): # Create a 2D DP table with n+1 rows and k+1 columns, initialized with False values dp = [[False] * (k+1) for _ in range(n+1)] # Base case: If k is 0, it is always possible to form an empty set, so set dp[i][0] to True for all i. for i in range(n+1): dp[i][0] = False # Base case: If n is 0, it is not possible to form a set with any sum, so set dp[0][j] to False for all j. for j in range(k+1): dp[0][j] = False # Base case: If k is 1, it is always possible to form a set with just one element equal to n, # so set dp[1][j] to True for all j. for j in range(1, k+1): dp[1][j] = True # Fill the DP table using bottom-up approach for i in range(1, n+1): for j in range(2, k+1): if i >= j: # If the current number i is greater than or equal to j, # we have two options: include i or exclude i to form the sum j. # dp[i-1][j] represents excluding i, and dp[i-j][j-1] represents including i. dp[i][j] = dp[i-1][j] or dp[i-j][j-1] else: # If the current number i is less than j, we can only exclude i to form the sum j. dp[i][j] = dp[i-1][j] # The final result is stored in dp[n][k], which represents whether it is possible to form a set of k distinct integers # whose sum is n. return dp[n][k]# Driver coden = 12k = 4if can_sum_to_distinct_integers(n, k): print("YES")else: print("No") |
C#
using System;public class GFG{ public static bool CanSumToDistinctIntegers(int n, int k) { // Create a 2D DP array to store the results of subproblems bool[,] dp = new bool[n + 1, k + 1]; // Initialize base cases for (int i = 0; i <= n; i++) { dp[i, 0] = false; } for (int j = 0; j <= k; j++) { dp[0, j] = false; } for (int j = 1; j <= k; j++) { dp[1, j] = true; } // Fill the DP array bottom-up for (int i = 1; i <= n; i++) { for (int j = 2; j <= k; j++) { if (i >= j) { dp[i, j] = dp[i - 1, j] || dp[i - j, j - 1]; } else { dp[i, j] = dp[i - 1, j]; } } } return dp[n, k]; } public static void Main() { int n = 12, k = 4; // Check if it is possible to form a sum of k distinct integers if (CanSumToDistinctIntegers(n, k)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } // To pause the console before exiting Console.ReadLine(); }} |
Javascript
// This function determines if it is possible to represent a given integer n// as the sum of k distinct positive integersfunction canSumToDistinctIntegers(n, k) { // Create a 2D array to store the DP table, with n+1 rows and k+1 columns let dp = new Array(n+1); for (let i = 0; i <= n; i++) { dp[i] = new Array(k+1).fill(false); } // Set base cases for (let i = 0; i <= n; i++) { dp[i][0] = false; } for (let j = 0; j <= k; j++) { dp[0][j] = false; } for (let j = 1; j <= k; j++) { dp[1][j] = true; } // Fill in the DP table using a nested loop for (let i = 1; i <= n; i++) { for (let j = 2; j <= k; j++) { if (i >= j) { dp[i][j] = dp[i-1][j] || dp[i-j][j-1]; } else { dp[i][j] = dp[i-1][j]; } } } // Return the result, which is stored in the last cell of the DP table return dp[n][k];}// Test the function with some sample inputlet n = 12, k = 4;if (canSumToDistinctIntegers(n, k)) { console.log("Yes");}else { console.log("No");} |
Output:
Yes
Time Complexity: O(nk), where n is the maximum possible value of n (the input number), and k is the maximum possible value of k
Auxiliary Space: O(nk) because we need to store the intermediate results in a 2D array.
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!
