Kann man meinen Code effizienter machen?

Complete the function that takes 3 numbers x, y and k

 (where x ≤ y), and returns the number of integers within the range [x..y]

(both ends included) that are divisible by k.

More scientifically: 

{ i : x ≤ i ≤ y, i mod k = 0 }

so braucht er halt zu lange, mir fällt aber nichts ein.

Answer 1

[BorisG2011]

Diese Aufgabe mit einer Schleife zu bearbeiten, ist für Intervalle, die sehr viele Ganzzahlen enthalten, nicht sinnvoll. Das Testbeispiel mit den Werten

x = 101, y = 2147483647, k = 11

veranschaulicht dies ja sehr deutlich. Eine sorgfältige Analyse der Aufgabe kann aber zu einer effizienten Lösung führen.

Erster Schritt:

Statt für aufeinanderfolgende Zahlen einfach nur auszurechnen, ob ein Divisionsrest Null ist, lohnt es sich, sich zu überlegen, was ein Divisionsrest und und was wir damit anfangen können.

1. Wenn der Divisionsrest x%k gleich Null ist, ist x durch k teilbar.
2. Wenn r = x%k größer als Null ist, ist x nicht durch k teilbar. Die Zahl (x - r) ist dann durch k teilbar und kleiner als x; die Zahl (x - r + k) ist ebenfalls durch k teilbar und größer als x. Von diesen beiden Zahlen interessiert uns aber nur die Zahl x1 = (x - r + k), weil dies die kleinste x nachfolgende Zahl ist, die durch k teilbar ist.
3. Wenn der Rest r = x%k negativ ist (in Java ist dies für positives k genau dann der Fall, wenn x negativ ist), addieren wir zu r den Teiler k, um den positiven Rest zu erhalten. Damit ist der Fall des negativen Rest auf den Fall des positiven Rests zurückgeführt.

Zweiter Schritt:

Nachdem wir die kleinste Zahl x1 bestimmt haben, die durch k teilbar ist und größer oder gleich x ist, prüfen wir zunächst, ob x1 kleiner oder gleich y ist. Wenn dies nicht der Fall ist, liegt x1 bereits außerhalb des Intervalls [x, y], was bedeutet, dass innerhalb des Intervalls überhaupt keine durch k teilbare Zahl zu finden ist.

Falls x1 kleiner oder gleich y ist, machen wir uns klar, dass die Folge der durch k teilbaren Zahlen, die x1 nachfolgen, gegeben ist durch den Ausdruck

$x_1\ +\ k\cdot nr$ wo nr eine natürliche Zahl ist.

Wir suchen nun das größe nr, für das der angegeben Ausdruck noch im gegebenen Intervall liegt. Dazu stellen die Ungleichung

$x_1\ +\ k\cdot nr\ \le\ y$ auf und lösen nach nr auf:

$nr\ =\ \frac{y\ -\ x_1}{k}$ Hier ist ganzzahliges Teilen zu verwenden; ein eventuell anfallender nichtnegativer Rest wird verworfen. Unter dieser Voraussetzung sagt uns nr, wie viele im Intervall [x, y] gelegene, durch k teilbare Zahlen, der Zahl x1 nachfolgen. Da die Zahl x1 ebenfalls durch k teilbar ist und im Intervall [x, y] liegt, muss nr um 1 vermehrt werden, um die Anahl aller im Intervall liegenden, durch k teilbaren Zahlen zu erhalten.

Mit diesen Vorüberlegungen läst sich nun ein Verfahren programmieren, das das Abzählen der Vielfachen in einer Schleife vollständig vermeidet:

/**
 *  Die Methode bestimmt die Anzahl der durch  k
 *  teilbaren Zahlen im Intervall [x, y].
 *  Voraussetzungen (nicht überprüft):
 *  x <= y,  k > 0
 */
public static long divisibleCount(long x, long y, long k) {
  long rest;
  long firstMultipleInInterval;

  rest = x % k;
  if (rest < 0) { // nichtnegativen Rest herstellen
     rest = k + rest;
  }
  if (rest == 0) {
     firstMultipleInInterval = x;
  } else {
     firstMultipleInInterval = x + (k - rest);
  };
  if (firstMultipleInInterval > y) {
     return 0;  //  keine im Intervall enthaltene
                //  Zahl ist durch  k teilbar
  } else {
     return (y - firstMultipleInInterval ) / k + 1;
  }
}

Bei Bedarf kann diese Methode auch für BigInteger umgeschrieben werden, wenn mit beliebig großen Ganzzahlen gerechnet werden muss..

Woher ich das weiß: Berufserfahrung – Berufstätigkeit als Software-Entwickler

Answer 2

[Schachpapa]

Wenn du tausend aufeinander folgende Zahlen hast, dann ist jede fünfte durch 5 teilbar. Also 200. Eventuell musst du ein bisschen mit Anfang und Ende spielen, da macht man gerne off-by-one-Fehler. Aber alle durchzählen und jede einzelne auf Teilbarkeit prüfen (prüfen, obwohl das Ergenis klar ist!) ist auf jeden Fall nicht das Gewünschte.

Woher ich das weiß: Berufserfahrung

Answer 3

[tunik123]

Wenn die drei Zahlen nichtnegativ sind, ist die gesuchte Anzahl

y / k - (x + k - 1) / k + 1

ansonsten müsste man vorher ein genügend großes Vielfaches von k addieren.

(Ich hoffe, Java behandelt die ganzzahligen Divisionen so wie C.)

Answer 4

[schnfz]

so braucht er halt zu lange, mir fällt aber nichts ein.

Ist das wirklich das Problem? Könnte der Testfall vielleicht daran scheitern, dass du grundlos zwischen int und long castest und somit (viel!) Wertebereich verlierst?

Aber davon abgesehen, du musst nicht jede Zahl im Intervall prüfen - überleg dir mal ein Beispiel.