Given two positive integers N and K, the task is to print the minimum count of numbers needed to get the sum equal to K, adding any element from the first N natural numbers only once. If it is impossible to get the sum equal to K, then print “-1“.
Examples:
Input: N = 5, K = 10
Output: 3
Explanation:
The most optimal way is to choose number {1, 4, 5} to which will sum up to 10.
Therefore, print 3 which is the minimum count of elements needed.Input: N = 5, K = 1000
Output: -1
Explanation:
It is impossible to get the sum equal to 1000.
Approach: The problem can be solved using the greedy algorithm. Follow the steps below to solve this problem:
- If K is greater than the sum of first N natural numbers, then the print “-1” and then return.
- If K is less than equal to N, then print 1 and then return.
- Otherwise, Initialize the variable say sum, and count as 0 to store the sum and minimum count of numbers needed.
- Iterate until N is greater than equal to 1 and sum is less than K and perform the following steps:
- Incrementing count by 1, sum by N, and then decrement the N by 1.
- Finally, if none of the above cases satisfy then print the count as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find minimum number of// elements required to obtain sum Kint Minimum(int N, int K){ // Stores the maximum sum that // can be obtained int sum = N * (N + 1) / 2; // If K is greater than the // Maximum sum if (K > sum) return -1; // If K is less than or equal // to N if (K <= N) return 1; // Stores the sum sum = 0; // Stores the count of numbers // needed int count = 0; // Iterate until N is greater than // or equal to 1 and sum is less // than K while (N >= 1 && sum < K) { // Increment count by 1 count += 1; // Increment sum by N sum += N; // Update the sum N -= 1; } // Finally, return the count return count;}// Driver Codeint main(){ // Given Input int N = 5, K = 10; // Function Call cout << (Minimum(N, K)); return 0;} // This code is contributed by Potta Lokesh |
Java
// Java program for the above approachimport java.io.*;// Function to find minimum number of// elements required to obtain sum Kclass GFG { static int Minimum(int N, int K) { // Stores the maximum sum that // can be obtained int sum = N * (N + 1) / 2; // If K is greater than the // Maximum sum if (K > sum) return -1; // If K is less than or equal // to N if (K <= N) return 1; // Stores the sum sum = 0; // Stores the count of numbers // needed int count = 0; // Iterate until N is greater than // or equal to 1 and sum is less // than K while (N >= 1 && sum < K) { // Increment count by 1 count += 1; // Increment sum by N sum += N; // Update the sum N -= 1; } // Finally, return the count return count; } // Driver Code public static void main(String[] args) { // Given Input int N = 5, K = 10; // Function Call System.out.println(Minimum(N, K)); }} |
Python3
# Python3 program for the above approach# Function to find minimum number of# elements required to obtain sum Kdef Minimum(N, K): # Stores the maximum sum that # can be obtained sum = N * (N + 1) // 2 # If K is greater than the # Maximum sum if (K > sum): return -1 # If K is less than or equal # to N if (K <= N): return 1 # Stores the sum sum = 0 # Stores the count of numbers # needed count = 0 # Iterate until N is greater than # or equal to 1 and sum is less # than K while (N >= 1 and sum < K): # Increment count by 1 count += 1 # Increment sum by N sum += N # Update the sum N -= 1 # Finally, return the count return count# Driver Codeif __name__ == '__main__': # Given Input N = 5 K = 10 # Function Call print(Minimum(N, K))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;// Function to find minimum number of// elements required to obtain sum Kclass GFG{static int Minimum(int N, int K){ // Stores the maximum sum that // can be obtained int sum = N * (N + 1) / 2; // If K is greater than the // Maximum sum if (K > sum) return -1; // If K is less than or equal // to N if (K <= N) return 1; // Stores the sum sum = 0; // Stores the count of numbers // needed int count = 0; // Iterate until N is greater than // or equal to 1 and sum is less // than K while (N >= 1 && sum < K) { // Increment count by 1 count += 1; // Increment sum by N sum += N; // Update the sum N -= 1; } // Finally, return the count return count;}// Driver Codestatic public void Main(){ // Given Input int N = 5, K = 10; // Function Call Console.Write(Minimum(N, K));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript implementation of// the above approach function Minimum(N, K) { // Stores the maximum sum that // can be obtained let sum = N * (N + 1) / 2; // If K is greater than the // Maximum sum if (K > sum) return -1; // If K is less than or equal // to N if (K <= N) return 1; // Stores the sum sum = 0; // Stores the count of numbers // needed let count = 0; // Iterate until N is greater than // or equal to 1 and sum is less // than K while (N >= 1 && sum < K) { // Increment count by 1 count += 1; // Increment sum by N sum += N; // Update the sum N -= 1; } // Finally, return the count return count; }// Driver Code // Given Input let N = 5, K = 10; // Function Call document.write(Minimum(N, K));</script> |
Output
3
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!
