Finde die Anzahl der Paare, bei denen das erste Element durch ein zweites Element teilbar ist

9

Angenommen, einige Zahlen gegeben

%Vor%

Sie müssen alle Paare finden (a, b) wobei a in der Liste vor b und a%b = 0 erscheint.

Hier sind solche Paare:

%Vor%

Gibt es einen besseren Algorithmus als O (n 2 ) ?

?     
Tahsin Rahman 17.08.2015, 06:28
quelle

2 Antworten

1

Sie können eine Liste aller Teiler der möglichen Ganzzahlen in der Eingabe = O (n ^ 1.5)

vorberechnen

Danach iterieren Sie über die Eingabe, während Sie verfolgen, wie viel eine Zahl wert ist (d. h. wie viele Paare es bilden würde).

Für jede Zahl in der Eingabe müssen Sie über alle Teiler iterieren, d. h. O (n ^ 1.5)

Also ist die Gesamtkomplexität O (n ^ 1.5), wobei n das Maximum von 100000 und die Größe Ihrer Eingabe ist.

%Vor%     
Stef 17.08.2015 08:55
quelle
0

Mit dynamischer Programmierung kann dies mit der Komplexität O (nlogn) gelöst werden. Ähnlich wie Münzwertproblem.

Bitte lesen Sie den folgenden Link für die Münzwertproblemlösung Problem der Münzbezeichnung

    
Himanshu Goel 17.08.2015 07:23
quelle

Tags und Links