Resolvendo problemas no Hackerrank: Divisible Sum Pairs

Por que em pt-br?

Eu vejo que a maioria dos materiais para resolução destes tipos de problemas estão em inglês. Infelizmente, sabemos que é uma minoria das pessoas que conseguem ter entendimento da língua inglesa aqui.

A ideia de escrever e explicar em português é preencher essa lacuna. Os enunciados dos problemas da maioria das plataformas estão em inglês, mas tentarei descrever ao máximo o problema em português.

Link para o problema: https://www.hackerrank.com/challenges/divisible-sum-pairs/problem

Enunciado

Given an array of integers and a positive integer , determine the number of pairs (i,j) pairs where i < j and ar[i] + ar[j] is divisible by k

Dado um array de inteiros e um número positivo, determine o número de pares (i,j) onde i < j e ar[i] + ar[j] é divisível por k.

Explicação do problema

Basicamente, a ideia é receber um array de números inteiros e um valor k e somando dois números. Caso este número seja divisível por k, então conta como um par. A função deve devolver o total de pares divisíveis por k.

Por exemplo, dado as entradas para função:

• arr = 1 3 2 1 6 2
• k = 3

Temos os seguintes pares divisíveis por 3:

• arr[0] + arr[2] = 1 + 2 = 3
• arr[0] + arr[5] = 1 + 2 = 3
• arr[1] + arr[3] = 3 + 6 = 9
• arr[2] + arr[4] = 2 + 1 = 3
• arr[4] + arr[5] = 1 + 2 = 3

Logo, a função deve retornar 5, pois temos 5 pares divisíveis por 3 (k).

Solucionando o problema

Força bruta (Brute Force)

A primeira vista e intuitivamente, como poderíamos resolver o problema?

Vamos fazer uma espécie de rascunho de como a função funcionaria:

• Iterar cada elemento da lista (vamos chamar o índice de elemento de i)
• Iterar todos os itens da esquerda deste elemento (i + 1 até o final da lista)
• Somar o elemento do índice i com cada item à sua esquerda. Caso seja divisível por k (ou seja, o resto da divisão seja 0), incremente um ao contador.
• No final, devolva o contador

Vale ressaltar alguns pontos positivos sobre essa solução:

• Ela atende a solução do problema, dado que no final sempre devolverá o valor total de pares divisíveis por k;
• O código e a ideia dela são extremamente simples de compreender.

Mas como nada é perfeito, infelizmente, ela tem um problema. Você conseguiu enxergar?

É necessário iterar o array diversas vezes. Para ficar mais claro, vamos usar o exemplo que estamos utilizando [1,3,2,1,6,2].

Abaixo segue uma demonstração exemplificando melhor:

Quando estivermos iterando na primeira posição (1), teremos que iterar também todos os itens à sua esquerda (3,2,1,6)

Quando estivermos iterando na segunda posição (3), teremos que adicioná-lo com todos os itens (2,1,6) à sua esquerda

Quando estivermos iterando na terceira posição (2), teremos que adicioná-lo com todos os itens (1,6) à sua esquerda e assim por diante

• Então na primeira iteração de i, são comparados os 4 elementos seguintes;
• Na segunda iteração, são comparados os 3 elementos à sua esquerda;

Então teremos 4 + 3 + 2 + 1 operações.

Isso é uma progressão aritmética. Esta entrada possui cinco elementos no array. Mas se fosse 10.000? Teríamos 9999 + 9998 + … + 1

Neste caso, a nossa função é de ordem quadrática, ou, O(n²). Isso é ruim =/

A ideia não é entrar em detalhes sobre isso, mas caso seja de interesse para melhor compreender o porquê essa função seria de ordem quadrática, nesse post explico o desempenho do selection sort.

Isso é o que chamamos de solução força bruta, pois estamos verificando todas as possibilidades para obter a solução.

Geralmente, primeiro fazemos uma solução de força bruta e depois tentamos melhorar.

Melhorando a nossa solução

Para entender como podemos melhorar uma solução, precisamos entender as propriedades que o problema nos dá e o que ele exatamente quer.

Vamos revisar alguns conceitos e o que é pedido pelo problema:

O que é um número divisível?

É um número o qual o resultado da divisão de um dividendo e um divisor o resto é zero.

Mas e um número não divisível?

É um número o qual o resultado da divisão de um dividendo e um divisor o resto não é zero.

Se um número não é divisível por k, de alguma forma eu conseguiria que números eu poderia somar para ele se tornar divisível?

Sim, e isso será a base para a melhoria do nosso algoritmo. Vamos explicar isso a seguir.

O que o problema pede?

A quantidade de pares somados tem que ser divisível por k.

Ok, sei que a maioria que está lendo deve saber de tudo isso, mas geralmente para melhorarmos uma solução, temos que saber bem as propriedades do problema, por mais óbvias que sejam.

No exemplo que estamos trabalhando, (k = 3 e arr = [1,3,2,1,6,2]), sabemos que ao dividirmos um número por 3, temos três possibilidades:

• O número ter resto 0 (ser divisível);
• O número ter resto 1 (não é divisível);
• O número ter resto 2(não é divisível);

Por exemplo, o número 1 dividido por 3, o quociente é 0 e o resto é 1. Agora vem a pergunta chave para melhorarmos nosso algoritmo: Que números somados a 1 o tornam divisíveis por 3?

Vamos validar as três hipóteses:

• Somar com um número de resto 0: Número 3. Sabemos que 3 + 1 = 4 que não é divisível por 3.
• Somar com um número de resto 1: Número 1. Sabemos que 1 + 1 = 2 que não é divisível por 3.
• Somar com um número de resto 2: Número 2. Sabemos que 1 + 2 = 3 que é divisível por 3

Parece que a terceira hipótese tem boas chances de ser válida. Faça o teste você mesmo. 5 também é um número de resto 2 e 5 + 1 é 6 que é divisível por 3. Ou seja 2,5,8,11… qualquer número de resto 2 vai torná-lo divisível por 3.

Agora, que tipo de números se somados fazem números de resto 2? Os de resto 1! Some 2 (resto 2) com 7 (resto 1), que você terá um número divisível por 3.

E os de resto zero? Somente com eles mesmo!

Bom, aqui já vimos um padrão. A soma dos restos sempre precisa ser 3 ou 0 para ser divisível!

Mas para resolver, ainda precisamos de alguma forma de “agrupar” esses números.

Para ficar mais claro, quando iterarmos o item 2 ([1,3,2,1,6,2]) temos que dividí-lo e encontrar quantos itens que já iteramos tem o complemento que ele precisa.

No exemplo acima, sabemos que o item já iteramos 1 e 3, que possuem respectivamente resto 1 e 0.

Então, podemos formar um par com [1,2], pois números com resto 2 somados com resto 1 são divisíveis por 1.

Para isso, podemos usar o conceito de bucket (balde), no qual armazenamos a contagem total de números agrupados por resto.

A seguir segue uma ilustração da ideia:

Na primeira iteração, verificamos que 1 / 3 tem resto 1 e os números que o fazem ser divisível por 3 (k) somados são números com resto 2. Porém, o bucket de resto 2 está vazio então não temos números que fazem pares com 1. No final, adicionamos 1 ao contador no bucket de resto 1, porque só precisamos saber a quantidade de números e não o número em si.

Na segunda iteração, verificamos que 3/ 3 tem resto 0e os números que o fazem ser divisível por 3 (k) somados são números com resto 0. Porém, o bucket de resto está vazio. Então, não temos números que fazem pares com 3. No final, adicionamos 1 ao contador no bucket de resto 0, porque só precisamos saber a quantidade de números e não o número em si.

Na terceira iteração, verificamos que 2 / 3 tem resto 2 e os números que o fazem ser divisível por 3 (k) somados são números com resto 1. Neste caso, sabemos que temos um item com resto 1 (adicionado nas iterações anteriores). Neste caso, sabemos que podemos formar um par (1,2), pois há um item no bucket de resto 1. Então, incrementamos o total de pares com a quantidade de itens naquele bucket. No final, adicionamos 1 ao contador no bucket de resto 2, porque só precisamos saber a quantidade de números e não o número em si.

Na quarta iteração, verificamos que 1 / 3 tem resto 1 e os números que o fazem ser divisível por 3 (k) somados são números com resto 2. Neste caso, sabemos que temos um item com resto 2(adicionado nas iterações anteriores). Sabemos que podemos formar um par (1,2) pela quantidade de itens no bucket. Então, incrementamos o total de pares com a quantidade de itens naquele bucket (1). No final, adicionamos 1 ao contador no bucket de resto 1, porque só precisamos saber a quantidade de números e não o número em si.

Na quinta iteração, verificamos que 6/ 3 tem resto 0 e os números que o fazem ser divisível por 3 (k) somados são números com resto 0. Neste caso, sabemos que temos um item com resto 0(adicionado nas iterações anteriores). Sabemos que podemos formar um par (3,6) pela quantidade de itens no bucket. Então, incrementamos o total de pares com a quantidade de itens naquele bucket (1). No final, adicionamos 1 ao contador no bucket de resto 1, porque só precisamos saber a quantidade de números e não o número em si.

Na sexta e última iteração, verificamos que 2/ 3 tem resto 2e os números que o fazem ser divisível por 3 (k) somados são números com resto 1. Neste caso, sabemos que temos dois itens com resto 1 (adicionado nas iterações anteriores). Sabemos que podemos formar dois pares ((1,2), (1,2)) pela quantidade de itens no bucket. Então, incrementamos o total de pares com a quantidade de itens naquele bucket (2). No final, adicionamos 1 ao contador no bucket de resto 2, porque só precisamos saber a quantidade de números e não o número em si.

Ao final, temos o total de pares e podemos retorná-lo.

Desempenho da solução final

Essa solução apesar de um pouco mais complexa que a inicial, é muito mais eficiente, pois só precisamos iterar o array uma vez e criar um novo array para agruparmos um contador para cada resto. A performance é O(n + k) que é linear.

Código

A seguir segue uma solução desenvolvida em Python para solucionar o problema.

Algorithms/divisible_sum_pairs.py at master · henriquebraga/Algorithms