## 🧠 Solução de leetcode até eu me tornar o top 1% – dia `57`

🔹 Problema: Consultas do produto de poderes de duas dificuldades: #MediumTags: #BITManipulação #PrefixProduct #ModularArithmetic 📝 Resumo do problema Resumindo: um número inteiro que pode ser expresso como uma soma de poderes distintos de dois (de sua representação binária). Várias perguntas, cada uma [l, r]representando índices na lista classificada de poderes de dois de n. Para cada consulta, calcule o produto de poderes de dois nessa faixa de índice, módulo 10^9 + 7. 🧠 Meu processo de pensamento Etapa 1: Compreender a estrutura de dados Cada n pode ser dividido em sua representação binária, onde cada 1 corresponde a uma potência de dois que compõem n. Exemplo: n = 10 (binário 1010) → poderes = [2, 8]

Digite o modo de tela completa Sair do modo de tela cheia Brute Force IDEA: Para cada consulta, atravesse os poderes de subarray[l:r] e multiplique os elementos, tomando módulo a cada vez. Isso funciona porque: o número de poderes é no máximo 32 (já que n ≤ 10^9). As consultas são aplicadas em uma lista muito pequena. Estratégia otimizada (não implementada aqui, mas possível): Modulo de produtos de prefixo pré -computação, para que cada consulta possa ser respondida no tempo O (1) em vez de O (comprimento da faixa) .Formula: Produto (L, R) = Prefixo[r] * Inverso (prefixo[l-1]) % Mod Digite o modo de saída de tela cheia de tela cheia, onde o inverso é calculado usando a exponenciação modular. Algoritmo usado: manipulação de bit para extrair poderes de duas + multiplicação modular. ⚙️ Solução da classe de Classe de Implementação de Código (Python): Def ProductQueries (self, n: int, consultas: Lista[List[int]]) -> Lista[int]: Mod = 10 ** 9 + 7 poderes = []
i = 0 # Extrato poderes de dois da representação binária de N enquanto (1 << i) <= n: se n & (1 << i): Powers.append (1 << i) i += 1 Resultado = []
Para L, r em consultas: Produto = 1 para J em Range (L, R + 1): Produto *= Powers[j]
Produto %= Mod Results.Append (Product) Resultados de retorno Digite Modo de tela cheia Saída Modo de tela cheia ⏱️ Tempo e complexidade do espaço 🧩 🧩 Takeaways ✅ Usando a representação binária é uma maneira limpa de extrair poderes de dois de um número inteiro. 💡 Como a lista de poderes é pequena (≤ 32), mesmo um loop de consulta de força bruta é rápido o suficiente. 💭 Para restrições maiores, os produtos prefixos + inversos modulares são o caminho a percorrer. 🔁 Reflexão (auto-verificação)

[x] Posso resolver isso sem ajuda?
[x] Eu escrevi código do zero?
[x] Eu entendi por que funciona?
[x] Serei capaz de lembrar isso em uma semana? 🚀 Progresso Rastreador Métrico Valor Dia 57 Problemas Total resolvidos 412 Confiança hoje 😃 Classificação do código de leetcode 1572

Fonte