Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You are a given a number N.

            N <= 10 ^ 9 .

You are given a range of numbers L and R .

               1 <= L , R <= 10 ^ 9.

You need to generate N by using numbers from L and R inclusive by adding them. You can use a number multiple times. For eg :

      test case : N  L  R
                  5   2   3    Yes N can be generated by using 2+3
                  7   4   5     NO , N can't be generated
                  45  9   11    Yes , using 9 five times
                  47  9   11    YES,  9*4 + 11 *1
                  48  9   11    Yes , 10*3 + 9*2
                  49  9   11    Yes , 9*1 + 10*4
share|improve this question
1  
You haven't actually asked a question. I don't count the title --- the question should be in the body, not just in the title. –  Gerry Myerson Feb 27 at 9:58

1 Answer 1

up vote 0 down vote accepted

Short answer

Assume $\gcd(L,R)=1$. We use the Extended Euclidean Algorithm to find $aL+bR=1$, where $a<0$. Then the solution is $$(aN+\lceil \tfrac{-aN}{R} \rceil R)L+(bN-\lceil \tfrac{-aN}{R} \rceil L)R=N$$ if $bN-\lceil \tfrac{-aN}{R} \rceil L$ is non-negative, otherwise a solution doesn't exist.

How it works

We can assume $L$ and $R$ are coprime (otherwise we divide $L$, $R$, and $N$ by $\gcd(L,R)$; if $\gcd(L,R)$ does not divide $N$, no solution exists).

Using the Extended Euclidean Algorithm, we find two integers $a$ and $b$ such that $$aL+bR=1$$ or equivalently $$(aN)L+(bN)R=N.$$ However, one of $a$ or $b$ will be negative (which is not allowed in this problem, as demonstrated by the $(7,4,5)$ case). Assume $a$ is negative (otherwise swap $L$ and $R$).

If it is possible that $xL+yR=N$ where $x$ and $y$ are both positive, then $(aN-x)L+(bN-y)R=0$, implying $aN \equiv x \pmod R$. So, $x$ (if it exists) is equal to $aN+kR$ for some $k \geq 1$.

This implies $$(aN+kR)L+(bN-kL)R=N.$$ So, we choose the smallest $k$ for which $aN+kR \geq 0$, which is $k=\lceil \tfrac{-aN}{R} \rceil$. If $bN-kL<0$, then no solution exists (with two positive coefficients), otherwise the solution is as given above.

Worked examples

  • When $N=5$ and $L=2$ and $R=3$, we have $(-1) \times L + 1 \times R = 1$, so $a=-1$ and $b=1$. We have $k=\lceil \tfrac{-(-1) \times 5}{3} \rceil=2$, and since $bN-kL=1 \times 5-2 \times 2=1>0$, we have the solution $$\overbrace{1}^{aN+kR} \times \overbrace{2}^L+\overbrace{1}^{bN-kL} \times \overbrace{3}^R=\overbrace{5}^N.$$

  • When $N=7$ and $L=4$ and $R=5$, we have $(-1) \times L + 1 \times R = 1$, so $a=-1$ and $b=1$. We have $k=\lceil \tfrac{-(-1) \times 7}{5} \rceil=2$, but $bN-kL=1 \times 7-2 \times 4=-1<0$, so no solution exists.

  • When $N=49$ and $L=11$ and $R=9$, we have $(-4) \times L + 5 \times R=1$, so $a=-4$ and $b=5$. We have $k=\lceil \tfrac{-(-4) \times 49}{9} \rceil=22$, and since $bN-kL=5 \times 49-22 \times 11=3>0$, we have the solution $$\overbrace{2}^{aN+kR} \times \overbrace{11}^L+\overbrace{3}^{bN-kL} \times \overbrace{9}^R=\overbrace{49}^N.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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