0
$\begingroup$

Given the values of $n, k, m$, you have to check if there are $m$ distinct numbers in the range from 1 to $k$ have the sum $n$ or not ?

$n$ represents the required sum $k$ represents numbers range(1,2,3,... to k). $m$ is the number of elements in the range from 1 to $k$ that has the sum $n$.

Example: n = 12, k = 8, m = 3 ==> there are 3 numbers in the range from 1 to 8 that have the sum 12 which are 2,3,7.

The problem is taken from hackerrank and called bonetrousle.

$\endgroup$
5
  • 2
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Sep 24 '16 at 18:04
  • 1
    $\begingroup$ Hi @Evil, don't worry it is a practice and I got to this stack to get algorithmic and scientific sense behind the problem. You can check the full code here github.com/PeterASteele/HackerRankProblems/blob/master/… $\endgroup$ Sep 24 '16 at 18:33
  • $\begingroup$ I think no as the problem stated above may have more solutions like. 3 4 5 ==> sum = 12 and 2 3 7 ==> sum = 12 $\endgroup$ Sep 24 '16 at 18:52
  • $\begingroup$ Unique was about the numbers to avoid situation where we can pick 12 = 4 + 4 + 4. $\endgroup$
    – Evil
    Sep 24 '16 at 19:08
  • $\begingroup$ yes the numbers should be unique. the answer 4 + 4 + 4 is incorrect. $\endgroup$ Sep 24 '16 at 19:24
5
$\begingroup$

Hint:

  1. What is the smallest number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?

  2. What is the largest number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?

  3. Can all numbers in between be so represented?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.