Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem…

Questão

Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i < j tais que V[i] + V[j] = k. Explique a ideia principal, as variáveis usadas e a complexidade temporal e espacial do procedimento.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Ideia principal: usar um conjunto (hash set) para registrar valores já vistos e verificar, para cada elemento x, se o complementar (k - x) já apareceu. Pseudocódigo (exemplo): fun existeParSoma(V, k): seen <- conjunto vazio para i de 0 até n-1: complemento <- k - V[i] se complemento está em seen: retornar verdadeiro inserir V[i] em seen retornar falso Variáveis: V (vetor de entrada), k (inteiro alvo), i (índice), complemento (inteiro), seen (conjunto/hash set). Complexidade: tempo médio O(n) porque cada verificação e inserção no hash set é O(1) amortizado; espaço O(n) no pior caso para armazenar seen. Alternativa: ordenar e aplicar dois ponteiros (tempo O(n log n), espaço O(1) adicional).

Explicação

A abordagem utiliza um conjunto para armazenar os elementos já vistos, permitindo verificar rapidamente se o complemento necessário para atingir a soma k já foi encontrado. Isso garante uma busca eficiente, com complexidade de tempo linear em média, já que cada operação de inserção e verificação no conjunto é rápida. A alternativa de usar dois ponteiros, embora válida, resulta em maior complexidade temporal devido à necessidade de ordenação prévia.

Raio-X da questão

Questões parecidas com resolução

• Projete, em pseudocódigo, um algoritmo que receba um vetor A[0..n-1] de inteiros e um inteiro alvo t, e retorne dois…
• Projete um algoritmo em pseudocódigo que, dado um vetor de números inteiros com tamanho par, percorra o vetor em pares…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a maior…
• Escreva um algoritmo em pseudocódigo que, dado um vetor V de n inteiros, construa dois vetores preservando a ordem…
• Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o comprimento do…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros, encontre o comprimento do maior subvetor…

Todas as questões de Programação - Linguagem de programação