Given $N$, $K$ and $S$, we have to find out a way to represent $S$ as a sum of exactly $K$ numbers between $1$ and $N - 1$. For example, if $S = 22$, $K = 7$ and $N = 10$, then one possible way is $3 + 3 + 3 + 3 + 3 + 3 + 4 = 22$. Is there any way to construct an algorithm that figures out one possible ways? I have figured out that if $K > S$ or $(N - 1)K < S$, then it won't be possible to do so. But given $K \leq S$ and $(N - 1)K \geq S$, what approach can I take to figure out one of the possible solutions?
Asked
Active
Viewed 125 times
1
-
Take $K-1$ $1's$ and then let the last summand be $S-(K-1)$. Thus, to write $13$ as the sum of exactly $6$ numbers we write $13=1+1+1+1+1+8$. – lulu Aug 06 '20 at 15:16
-
Where did the $13$ come from? @lulu – Robur_131 Aug 06 '20 at 15:52
-
I made up that example to illustrate my (very simple) algorithm. – lulu Aug 06 '20 at 17:17
1 Answers
1
If we donote $\lfloor x\rfloor$ the entire part of $x$ and $\{x\}$ the fractional part of $x$, you can let $n=\left\lfloor\frac{S}{K}\right\rfloor,\,k=\left\{\frac{S}{K}\right\}\cdot K$ and take $k$ times $n+1$ and $K-k$ times $n$. $$k\cdot(n+1)+(K-k)\cdot n= K\cdot\left\lfloor\frac{S}{K}\right\rfloor+ \left\{\frac{S}{K}\right\}\cdot K=\frac{S}{K}\cdot K=S$$
Alexey Burdin
- 5,214
-
-
Sure. $n,k$ is the entire part and the remainder of dividing $S/K$. – Alexey Burdin Aug 06 '20 at 18:31
-
Could you illustrate an example? I'm having a little bit of trouble understanding. – Robur_131 Aug 06 '20 at 18:59
-
Take $S=22,,K=7$ from the OP. $n=\left\lfloor\frac{22}{7}\right\rfloor=3$, $k=1$ thus you take $k=1\quad$ $4$s ($n+1=4$) and $K-k=6\quad$ $3$s. – Alexey Burdin Aug 06 '20 at 19:37
-
Thank you for your answer. But is there any proof or intuitive way of coming up with this answer that I can keep in mind for future? @Alexey Burdin – Robur_131 Aug 07 '20 at 08:58
-
It was based on the construction in the OP, just expressed more mathematically. I began to thinking like that "what is $3$ there? why $3$? how comes $3$ $6$ times and $4$ $1$ time?" – Alexey Burdin Aug 07 '20 at 11:43
-
1