Mittel 2 gelöst 100.0% Erfolgsquote

Recursive Power

Compute a power recursively by halving the exponent.

Das lernst du

  • Den Exponenten bei jedem Aufruf halbieren
  • Basisfälle für die Rekursion schreiben
  • Von linearer zu logarithmischer Zeit kommen

Problem

Compute base to the power exponent with recursion: x⁰ = 1, and xⁿ = (x^(n/2))² for even n or x × (x^((n−1)/2))² for odd n. This uses far fewer multiplications than a simple loop.

Implement recursive_power(base, exponent).

Input

base: The base. exponent: The exponent (zero or positive).

Output

Return base raised to exponent.

Einschränkungen

-10 ≤ base ≤ 10; 0 ≤ exponent ≤ 18

Beispiele

Beispiel 1
Eingabe:
base = 3
exponent = 5

Erwartete Ausgabe:
expected = 243
Eingabe:
long long base = 3;
long long exponent = 5;

Erwartete Ausgabe:
long long expected = 243;
Eingabe:
long base = 3;
long exponent = 5;

Erwartete Ausgabe:
long expected = 243;

Erläuterung

3⁵ = 3 × (3²)² = 3 × 81 = 243.

Beispiel 2
Eingabe:
base = 7
exponent = 0

Erwartete Ausgabe:
expected = 1
Eingabe:
long long base = 7;
long long exponent = 0;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long base = 7;
long exponent = 0;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

The base case: anything to the power 0 is 1.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Nutze die Parität des Exponenten, um das Problem schnell zu verkleinern.

Hinweis 2

Rekursive Quadratur vermeidet doppelte Arbeit und reduziert die Zahl der Multiplikationen stark.

Hinweis 3

Achte auf den Exponenten 0 und den Basisfall für kleine Exponenten.

Erwartete Komplexität

Zeit O(log exponent), zusätzlicher Speicher O(log exponent)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 820 ms - 5/5 Code ansehen
2 LMLaura Mahlow Python 829 ms - 3/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.