Resolvendo problemas no HackerRank: Subconjuntos não divisíveis

Olá, seja bem vindo a mais um Resolvendo problemas no HackerRank: No caso de hoje, analisar valores que estão dentro de um array e se a soma de subconjuntos criados por eles pode ser divisível por um valor de k. Vejamos mais informações com a explicação detalhada e sua resolução.

Non-Divisible Subset -

Dado um conjunto de inteiros distintos, imprima o tamanho de um subconjunto máximo de S onde a soma de 2 números em S´ não é divisível por k. Veja o exemplo:

• S = [1, 2, 3, 4, 5, 6]
• K = 3

Aqui, podemos formar um subconjunto maximal de S como S´= [ 3 , 1, 4 ]. Para verificar, podemos pegar todos os pares possíveis de elementos de S` e verificar se a soma de quaisquer dois elementos é divisível por k = 3 ou não.

Aqui 3 + 1 = 4, que não é divisível por 3. Além disso, 3 + 4 = 7 também não é divisível por 3. E outro par possível que podemos verificar é 1+4 = 5, que também não é divisível por 3. Portanto, satisfaz a condição!

Vejamos o código:

`
function nonDivisibleSubset(k, s) {
// Write your code here
let answer = 0;
let arr = new Array(k).fill(0);

s.map(val => {
  arr[val % k]++;
})


if (arr[0] > 0) answer++;
for (let i = 1; i < k; i++) {
    if (arr[i] == 0) continue;
    if (i + i == k) answer++;
    else {
        answer += Math.max(arr[i], arr[k - i])
        arr[i] = 0;
        arr[k - i] = 0;
    }
}
return answer;

}
`

O código começa inicializando uma variável "answer" com o valor zero e cria um array chamado "arr" com k posições, preenchendo todas com zero.

Em seguida, a função percorre o array s e, para cada elemento, incrementa em 1 a posição do array "arr" correspondente ao resto da divisão do elemento por k. Esse processo serve para contar quantos elementos de s têm cada resto de divisão por k.

Após contar quantos elementos de s têm cada resto de divisão por k, a função verifica se há algum elemento no array s que é divisível por k (isto é, tem resto de divisão igual a zero). Se houver, incrementa a variável "answer" em 1.

Em seguida, a função percorre o array "arr" do índice 1 até o índice k-1. Para cada índice i, a função verifica se existe algum elemento no array "arr" correspondente à posição k-i. Se existir, significa que um subconjunto pode ser formado com elementos que têm resto de divisão igual a i ou k-i, já que a soma desses restos é igual a k.

Nesse caso, a função incrementa a variável "answer" com o valor máximo entre a quantidade de elementos com resto de divisão igual a i e a quantidade de elementos com resto de divisão igual a k-i. Depois disso, a função zera as posições do array "arr" correspondentes aos restos de divisão igual a i e k-i.

Por fim, a função retorna o valor de "answer", que representa o tamanho do maior subconjunto de elementos de s que não são divisíveis por k.

O resultado será:

`
4 3
1 7 2 4

input -> 3
`

Assim, concluímos mais um _Resolvendo problemas no HackerRank: _até a próxima.