Médio 2 resolvidos 100.0% de aceitação

Recursive Power

Compute a power recursively by halving the exponent.

O que você vai aprender

  • Dividir o expoente pela metade a cada chamada
  • Escrever casos base para a recursão
  • Passar de tempo linear para logarítmico

Problema

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.

Restrições

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

Exemplos

Exemplo 1
Entrada:
base = 3
exponent = 5

Saída esperada:
expected = 243
Entrada:
long long base = 3;
long long exponent = 5;

Saída esperada:
long long expected = 243;
Entrada:
long base = 3;
long exponent = 5;

Saída esperada:
long expected = 243;

Explicação

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

Exemplo 2
Entrada:
base = 7
exponent = 0

Saída esperada:
expected = 1
Entrada:
long long base = 7;
long long exponent = 0;

Saída esperada:
long long expected = 1;
Entrada:
long base = 7;
long exponent = 0;

Saída esperada:
long expected = 1;

Explicação

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

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Use a paridade do expoente para reduzir rapidamente o tamanho do problema.

Dica 2

A exponenciação recursiva evita trabalho repetido e corta drasticamente o número de multiplicações.

Dica 3

Cuidado com o expoente zero e com o caso base para expoentes pequenos.

Complexidade esperada

tempo O(log exponent), espaço extra O(log exponent)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 ННикита Python 820 ms - 5/5 Ver código
2 LMLaura Mahlow Python 829 ms - 3/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 2 soluções completas abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.