zunehmende Codeleistung von codility

Question

heute hörte ich von dieser Web site, die codility genannt wird, in der ein Benutzer verschiedene programmierenprüfung geben kann, um ihre Code-Leistung zu überprüfen.

Als ich anfing, sie schenkte mir dieser Probe Test,

Aufgabenbeschreibung Ein kleiner Frosch will auf die andere Seite der Straße bekommen. Der Frosch befindet sich derzeit an Position X und möchte eine Position größer oder gleich Y erreichen. Der kleine Frosch springt immer einen festen Abstand, D. Zählen Sie die minimale Anzahl von Sprüngen, die der kleine Frosch ausführen muss sein Ziel.

Schreibe eine Funktion: class Solution { public int solution(int X, int Y, int D); } , die, da drei ganzen Zahlen X, Y und D, die minimale Anzahl von Sprüngen von Position X zu einer Position, die gleich oder größer als Y zurückgibt.

Zum Beispiel gegeben:
X = 10
Y = 85
D = 30 die Funktion 3 zurückkehren soll, weil der Frosch wird wie folgt angeordnet werden:

nach dem ersten Sprung, an Position 10 + 30 = 40

nach dem zweiten Sprung, bei Position 10 + 30 + 30 = 70

nach dem dritten Sprung, an Position 30 + 10 + 30 + 30 = 100

annehmen, daß: X, Y und D ganze Zahlen sind im Bereich

[1..1,000,000,000]; X ≤ Y. Komplexität: erwartete Worst-Case-Zeit

Komplexität ist O (1); Die erwartete Worst-Case-Raumkomplexität ist O (1).

Die Frage war recht einfach und es hat mich wie 2 Minuten die Lösung zu schreiben, die folgende ist,

class Solution { 
    public int solution(int X, int Y, int D) { 

     int p = 0; 
     while (X < Y){ 
      p++; 
      X = X + D; 
     } 
    return p; 
    } 
} 

das Testergebnis zeigt jedoch, dass die Leistung meiner Code ist nur 20% und ich erzielte nur 55%,

Hier ist der Link führt, https://codility.com/demo/results/demo66WP2H-K25/

Das war so einfach Code, wo ich gerade eine einzige while Schleife verwendet habe, wie könnte es möglicherweise viel schneller machen?

Answer 1

Grund math:

X + nD >= Y 
nD >= Y - X 
n >= (Y - X)/D 

Der Mindestwert für n wird das Ergebnis der Aufrundung der Teilung (Y - X) von D.

Big O-Analyse für diese Operation:

• Komplexität: O (1). Es ist ein Unterschied, eine Abteilung und eine Aufrundung
• Worst-Case-Raumkomplexität O (1): Sie können maximal 3 weitere Variablen:
  • Unterschied für Y - X, lassen Sie uns dies zuweisen in Z.
  • Division zwischen Z von D, lassen Sie uns dies in E zuweisen.
  • Runden E up, lassen Sie uns dies in R (aus dem Ergebnis) zuweisen.

Answer 2

class Solution { 
    public int solution(int x, int y, int d) { 
     // write your code in Java SE 8 
     System.out.println("this is a debug message"+(y-x)%d); 
     if((y-x)%d == 0) 
      return ((y-x)/d); 
     else 
      return (((y-x)/d)+1); 
    } 
} 

Answer 3

JavaScript-Lösung 100/100

function solution (x,y,d) { 
    if ((y-x) % d === 0) { 
     return (y-x)/d; 
    } else { 
     return Math.ceil((y-x)/d); 
    } 
} 

Answer 4

Hier Scala Lösung:

def solution(X: Int, Y: Int, D: Int): Int = { 

    //divide distance (Y-X) with fixed jump distance. If there is reminder then add 1 to result to 
    // cover that part with one jump 

    val jumps = (Y-X)/D + (if(((Y-X) % D) >0) 1 else 0) 

    jumps 

    } 

Performance: https://codility.com/demo/results/trainingTQS547-ZQW/

Answer 5

C# 100 erhielt 10 von 0 Punkte

using System; 
// you can also use other imports, for example: 
// using System.Collections.Generic; 

// you can write to stdout for debugging purposes, e.g. 
// Console.WriteLine("this is a debug message"); 

class Solution { 
    public int solution(int X, int Y, int D) { 

     int Len= Y-X; 
     if (Len%D==0) 
     { 
      return Len/D; 
     } 
     else 
     { 
      return (Len/D)+1; 
     } 
    } 
} 

Answer 6

class Solution { 
    public int solution(int x, int y, int d) { 
    return (y - x + d - 1)/d; 
    } 
} 

Answer 7

Java (eine Zeile), Correctness 100%, Leistung 100%, Task-Score 100%

// you can also use imports, for example: 
// import java.util.*; 

// you can write to stdout for debugging purposes, e.g. 
// System.out.println("this is a debug message"); 

class Solution { 
    public int solution(int X, int Y, int D) { 
     return (int) Math.ceil((double) (Y - X)/(double) D); 
    } 
}