Math Erklärung, warum dieser Code funktioniert

Question

Ich habe ein Problem in der Website CodeFights, die ich mit zwei Schleifen gelöst. Während ich auf eine andere Antwort schaute, fand ich eine, die es ohne Schleifen löste und es ließ mich mit offenem Mund zurück. Der Programmierer hat Math.min/max angewendet, und obwohl ich verstehe, was der Code tut, verstehe ich nicht, warum er funktioniert.

Ich liebe es zu lernen, denn hey, Math.max/min schlägt sicher die Bytes aus meinen Loops.

Given integers n, l and r, find the number of ways to represent n as a sum 
of two integers A and B such that l ≤ A ≤ B ≤ r. 

Example 

For n = 6, l = 2 and r = 4, the output should be 
countSumOfTwoRepresentations2(n, l, r) = 2. 

There are just two ways to write 6 as A + B, where 2 ≤ A ≤ B ≤ 4: 6 = 2 + 4 and 6 = 3 + 3. 

Input/Output 

[time limit] 4000ms (js) 
[input] integer n 

A positive integer. 

Constraints: 
5 ≤ n ≤ 109. 

[input] integer l 

A positive integer. 

Constraints: 
1 ≤ l ≤ r. 

[input] integer r 

A positive integer. 

Constraints: 
l ≤ r ≤ 109, 
r - l ≤ 106. 

Der erstaunliche Antwort des Coder:

function countSumOfTwoRepresentations2(n, l, r) { 
    return Math.max(Math.min(Math.floor(n/2) - l, r - Math.ceil(n/2)) + 1, 0); 
} 

Mein Mist im Vergleich:

function countSumOfTwoRepresentations2(n, l, r) { 
    var representations = 0; 
    //Only travel the loop until n/2 , because l+r will never equal n 
    // if l or r > n/2 
    var limit = Math.floor(n/2); 
    for(var i=l; i<=r && i<=limit; ++i){ 
     for(var j=i;j<=r;++j){ 
      if(i+j == n){ 
       ++representations; 
       break; 
      } 
     } 
    } 
    return representations; 
} 

Answer 1

Bei ganzen Zahlen n, l und r, die Anzahl der Wege finden, um darzustellen n als eine Summe von zwei Ganzzahlen A und B wie z dass l ≤ A ≤ B ≤ r.

Zunächst betrachten, dass, wenn n gerade und lassen x = n/2, wir haben mindestens eine Lösung (x + x), wenn und nur wenn, l ≤ x ≤ r. Wenn x nicht in diesem Bereich ist, dann gibt es keine Lösung, da entweder x < l und l + l > n oder r < x und r + r < n.

Das kann auf gerade oder ungerade n verallgemeinert werden: Es gibt eine Lösung, wenn und nur wenn: . Wenn wir A = floor(x) und B = ceil(x) zulassen, ist diese Lösung A + B. Jede andere Lösung kann gefunden werden, indem ein Schritt entlang der Zahlenlinie weg von diesem Punkt in jeder Richtung unternommen wird. (A - 1) + (B + 1) = A + B = n, daher ist (A - 1) + (B + 1) eine Lösung, solange (A - 1) die l Grenze nicht überschritten hat und (B + 1) die r Grenze nicht überschritten hat. Also, wenn Sie eine Lösung mit nur einer Schleife will man so etwas tun könnte:

function countSumOfTwoRepresentations2(n, l, r) { 
    var x = n/2; 
    var A = Math.floor(x); 
    var B = Math.ceil(x); 
    for (var count = 0; l <= A && B <= r; count++) { 
     A--; 
     B++; 
    } 
    return count; 
} 

Aber wie oft hat die Schleife durchlaufen? Nun, es durchläuft, bis eine der Anhaltebedingungen geschieht:

1. A kleiner als l
2. B größer als r

Wenn 1. geschieht zuerst, dann durchläuft es Math.floor(x) - l + 1 mal, während bei 2. passiert zuerst es iteriert r - Math.ceil(x) + 1 (wenn beide Bedingungen in der gleichen Iteration auftreten, dann Math.floor(x) - l === r - Math.ceil(x)).

Solange es eine Lösung, die Schleife iteriert die kleineren von Math.floor(x) - l + 1 oder r - Math.ceil(x) + 1 Zeiten, die ist, wo die Codierer die Antwort Math.min(Math.floor(n/2) - l, r - Math.ceil(n/2)) + 1 aus erhielten (nach x zurück zum n/2 Substitution und die + 1 aus jedem Term ziehen und Zugabe nachher statt.

Wenn es keine Lösung gibt, EG. n = 10, l = 20, r = 20, wird diese Formel ein negatives Ergebnis geben, aber es sollte stattdessen 0 geben, weshalb er Math.max(result, 0); hinzugefügt.

Aus Gründen der Übersichtlichkeit der Lösung des Coder könnte als (noch ohne Schleifen) geschrieben werden:

function countSumOfTwoRepresentations2(n, l, r) { 
    var x = n/2; 
    var A = Math.floor(x); 
    var B = Math.ceil(x); 

    // Every solution is of the form (A - i) + (B + i), where i is an integer >= 0 

    // How many values of i are valid for l <= (A - i) 
    var stepsA = A - l + 1; 

    // How many values of i are valid for (B + i) <= r 
    var stepsB = r - B + 1; 

    // If the formulas gave a negative amount of valid steps, 
    // there is no solution, so return 0 
    if (stepsA < 0 || stepsB < 0) 
     return 0; 

    // Otherwise, return the smaller valid amount of steps, 
    // that is the number of steps that are valid for both A and B 
    return Math.min(stepsA, stepsB); 
}