# Minimum count of numbers needed from 1 to N that yields the sum as K

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 = 10Output:3Explanation:

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 = 1000Output:-1Explanation:

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**,**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**.

- Incrementing
- 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 K` `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 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` `int` `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 approach` `import` `java.io.*;` `// Function to find minimum number of` `// elements required to obtain sum K` `class` `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 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 K` `def` `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 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 Code` `if` `__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 approach` `using` `System;` `// Function to find minimum number of` `// elements required to obtain sum K` `class` `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 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` `static` `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 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)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**