1
$\begingroup$

I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example

   read number 1
   read number 2
   read final number 3

There are 17 ways how to achieve 500 with those two numbers e.g 

10*2 + 15*32

and so on , the code for this is pretty simple

 i_max=final_number/number1
 j_max=final_number/number2
for(i=0;i<i_max;i++){

     for(j=0;j<j_max;j++){
             count=number1 * i;
              count_two = number 2 * j;
               if(count+count_two==final_number){
                    //print it
}
}}

This code works fine , but the problem is when i input large numbers like

number1=100
number2=500
final_number=50000000

in this case , the computer takes very long time to count/find/print all possible ways. Is there any way to make alghoritm for this as fast for big numbers too? I have found out that the better way and fastest is not to increment i by 1 but by whole number or whole number /2 and sometimes both of them ; but how can i decide if i should add whole number or just half of the number to the i/j?

I tred to write in as much in pseudo code as i could

Also , i find out the second loop does not have to start always from 0/max number everytime it gets triggered , so 

for i=0 ; i<max_number1;i++
  for j=max_number2;j>=0;j--
    if number1*i + number2*j == final number
     max_number 2 = j

But i still fail to find when should i add whole number and when just half of it, I tried to increment first number by half of number2 , and second number by 1 until it finds match and then adding whole numbers , but this didnt work as i expected it worked for larger numbers but for numbers like

10 13 100 it said there is now way to combine first two and make 100 while there is a one 10 * 10 + 13 * 0

On request / for those who got lost in my explanation = i input 3 random numbers e.g 10 13 749 and i want to find out how many combinations of first two nubmers

10
13

would get result 749 it made it with nested loops

for(j=0;j<j_max;j++){
                 count=number1 * i;
                 count_two = number 2 * j;
                   if(count+count_two==final_number){
                        //print it
    }
    }}

which works but takes very long time to calculate if i input large numbers , for things i have tried or come up with read whole post.

Full example = number 1=757 number 2=989 final number = 56899148 There is 77 way how to combine first two numbers into the final one and those are

757 * 0 + 989 * 57532
 757 * 989 + 989 * 56775
 757 * 1978 + 989 * 56018
 757 * 2967 + 989 * 55261
 757 * 3956 + 989 * 54504
 757 * 4945 + 989 * 53747
 757 * 5934 + 989 * 52990
 757 * 6923 + 989 * 52233
 757 * 7912 + 989 * 51476
 757 * 8901 + 989 * 50719
 757 * 9890 + 989 * 49962
 757 * 10879 + 989 * 49205
 757 * 11868 + 989 * 48448
 757 * 12857 + 989 * 47691
 757 * 13846 + 989 * 46934
 757 * 14835 + 989 * 46177
 757 * 15824 + 989 * 45420
 757 * 16813 + 989 * 44663
 757 * 17802 + 989 * 43906
 757 * 18791 + 989 * 43149
 757 * 19780 + 989 * 42392
 757 * 20769 + 989 * 41635
 757 * 21758 + 989 * 40878
 757 * 22747 + 989 * 40121
 757 * 23736 + 989 * 39364
 757 * 24725 + 989 * 38607
 757 * 25714 + 989 * 37850
 757 * 26703 + 989 * 37093
 757 * 27692 + 989 * 36336
 757 * 28681 + 989 * 35579
 757 * 29670 + 989 * 34822
 757 * 30659 + 989 * 34065
 757 * 31648 + 989 * 33308
 757 * 32637 + 989 * 32551
 757 * 33626 + 989 * 31794
 757 * 34615 + 989 * 31037
 757 * 35604 + 989 * 30280
 757 * 36593 + 989 * 29523
 757 * 37582 + 989 * 28766
 757 * 38571 + 989 * 28009
 757 * 39560 + 989 * 27252
 757 * 40549 + 989 * 26495
 757 * 41538 + 989 * 25738
 757 * 42527 + 989 * 24981
 757 * 43516 + 989 * 24224
 757 * 44505 + 989 * 23467
 757 * 45494 + 989 * 22710
 757 * 46483 + 989 * 21953
 757 * 47472 + 989 * 21196
 757 * 48461 + 989 * 20439
 757 * 49450 + 989 * 19682
 757 * 50439 + 989 * 18925
 757 * 51428 + 989 * 18168
 757 * 52417 + 989 * 17411
 757 * 53406 + 989 * 16654
 757 * 54395 + 989 * 15897
 757 * 55384 + 989 * 15140
 757 * 56373 + 989 * 14383
 757 * 57362 + 989 * 13626
 757 * 58351 + 989 * 12869
 757 * 59340 + 989 * 12112
 757 * 60329 + 989 * 11355
 757 * 61318 + 989 * 10598
 757 * 62307 + 989 * 9841
 757 * 63296 + 989 * 9084
 757 * 64285 + 989 * 8327
 757 * 65274 + 989 * 7570
 757 * 66263 + 989 * 6813
 757 * 67252 + 989 * 6056
 757 * 68241 + 989 * 5299
 757 * 69230 + 989 * 4542
 757 * 70219 + 989 * 3785
 757 * 71208 + 989 * 3028
 757 * 72197 + 989 * 2271
 757 * 73186 + 989 * 1514
 757 * 74175 + 989 * 757
 757 * 75164 + 989 * 0

Again this works , but with very big numbers it takes lot of time to actually calculate it.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ This is a nice exercise, but you should try to solve it yourself. Hint: If the first term is 10*2, what does the second term have to look like? Is this true if you replace 2 with any other number? If not, which values is it true for? Note that code is off-topic here; please replace the code with ideas and/or algorithms (pseudocode) . $\endgroup$ – D.W.♦ Nov 7 '15 at 9:44
  • $\begingroup$ yes in this case its pretty obvious , but i need to find way how to make it fast for all inputs > 0 , in other cases its not so obvious and i fail to find the way $\endgroup$ – user3424358 Nov 7 '15 at 9:56
  • 1
    $\begingroup$ OK -- then I suggest you edit the question to show what you've worked out so far and how far you got along that line where you got stuck... especially, which cases you can handle and which ones are not obvious to you. $\endgroup$ – D.W.♦ Nov 7 '15 at 10:10
  • 3
    $\begingroup$ From your question, it's not clear to me what the problem you are trying to solve is exactly. Please give a precise definition. $\endgroup$ – Raphael♦ Nov 7 '15 at 11:08
  • 1
    $\begingroup$ Examples are not a substitute for a concise and precise description. (Also, your title does not seem to relate to the problem you describe, at all.) $\endgroup$ – Raphael♦ Nov 7 '15 at 23:48
1
$\begingroup$

With inputs $n_1,n_2,n_3$, you want to find all positive integers $(a,b)$ such that $an_1+bn_2 = n_3$ You observed that for even moderately large inputs, your two nested loops with a test to see if you come up with a solution takes a long time. It you apply a bit of number theory, there's an algorithm that is very much faster.

  1. First, find the greatest common divisor of $n_1$ and $n_2$. The extended euclidean algorithm is not only very fast (using a number of steps proportional to the number of digits in the larger of the two numbers), but also provides a way to do the next step. If $g=\gcd(n_1,n_2)$ divides $n_3$, continue to the next step, otherwise there will be no solutions to your problem, so quit.
  2. The extended Euclidean algorithm will give you integer solutions, $a, b$ to $$ an_1+bn_2=g $$ In what follows, we'll assume $g=1$ for simplicity. If it's not, just divide $n_1,n_2,n_3$ by $g$ and carry on as below. We'll then have $$ (an_3)n_1+(bn_3)n_2 = n_3 $$ You're getting close to a solution, but $an_3$ or $bn_3$ might not both be positive, so we'll need some other solution. Observe that for any integer $k$, $$\begin{align} & (an_3-kn_2)n_1+(bn_3+kn_1)n_2\\ =&\ (an_3)n_1-kn_2n_1+(bn_3)n_2+kn_1n_2\\ =&\ (an_3)n_1+(bn_3)n_2 = n_3 \end{align}$$ so $an_3-kn_2$ and $bn_3+kn_1$ will also be solutions, for any integer $k$.
  3. Now all we have to do is pick $k$ values such that $$ an_3-kn_2\ge 0\quad\text{and}\quad bn_3+kn_1\ge 0 $$ In other words, all we have to do is loop through the integers $k$ such that $$ -\frac{bn_3}{n_1}\le k\le\frac{an_3}{n_2} $$

Edit: There's a potential problem here, though: it might be that some of the intermediate calculations might be too large to avoid integer overflow. Let's see if we can keep everything no larger than $n_3$. We could let $k=a\lfloor n_3/n_2\rfloor$ and it's not hard to show that $$ a'=an_3-kn_2=an_3-a\left\lfloor\frac{n_3}{n_2}\right\rfloor n_2>0 $$ and then let $$ b'=\frac{n_3-a'n_1}{n_2} $$ we will have found a solution, $(a',b')$ to $$ a'n_1+b'n_2=n_3 $$ which was our goal.

Here's how it would work for an example almost like yours with $n_1=989$, $n_2=757$, $n_3=56899150$.

First, find $\gcd(989,757)=1$, and we find from the extended Euclidean algorithm that $$ 1=(62)989+(-81)757 $$ so we let $$\begin{align} a'&=62\left(56899150-757\left\lfloor\frac{56899150}{757}\right\rfloor\right)\\ &= 62(56899150-757\cdot75164)\\ &= 62(56899150-56899148)\\ &= 62\cdot 2 = 124 \end{align}$$ and we also find that $b'=75002$, so we'll have solutions $(a',b')$ given by $$\begin{array}{cc} a' & b'\\ 124 & 75002 \\ 881 & 74013 \\ 1638 & 73924 \\ \vdots & \vdots \\ 56899 & 827 \end{array}$$ where each row in the solution is the previous row solution for $a'$ plus 757 and the previous row solution for $b'$ minus 989, stopping when the $b'$ solution is negative.

Improve this answer
$\endgroup$
5
  • $\begingroup$ as previous one great explanation , but what would be the result = amount of combinations? in this case it should be 76 $\endgroup$ – user3424358 Nov 10 '15 at 21:49
  • $\begingroup$ In this example, once we find $(a',b')$, the $a'$ will be the smallest possible, so we require $b'>0$ and ask how many multiples of 989 will it take to drive $b'$ to its smallest positive value? Just divide $b'$ by 989, so $75002=(75)989+827$ so 75 steps will take $b'$ down as small as possible, plus 1 for the original $(a',b')=(124,75002)$ or, indeed 76 values, as you indicated. BTW, I've spent a lot of time on this, so if you find it helpful, it might be a good idea to reward me by clicking the green check mark to accept the answer. $\endgroup$ – Rick Decker Nov 10 '15 at 22:06
  • $\begingroup$ hopefully last question how did u get the value of b`? with same method as for a its around 160 $\endgroup$ – user3424358 Nov 12 '15 at 20:05
  • $\begingroup$ @user3424358. Since we know that $an_1+bn_2=1$ in this case, we have $b=(1-an_1)/n_2$ and we also know $b'=bn_3$. Take it from there. $\endgroup$ – Rick Decker Nov 12 '15 at 21:04
  • $\begingroup$ im afraid , this method does not work either for big numbers if you wanted to try it - 5098109 , 25279297 ,36821491225502191 and 286 is should be result $\endgroup$ – user3424358 Nov 12 '15 at 22:25

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.