Como Penso e Resolvo "Distribute Candies Among Children II" em Elixir

Um Guia Completo da Força Bruta ao Domínio Combinatório

Quando encaro um problema do LeetCode, sigo sempre o mesmo processo mental: entender o problema, começar pela solução correta mais simples e depois otimizar encontrando a estrutura matemática por baixo. O problema Distribute Candies Among Children II é um estudo de caso perfeito para isso, porque nos leva dos loops aninhados às estrelas e barras até a inclusão-exclusão — um caminho que revela a conexão profunda entre programação e combinatória.

Este artigo percorre essa jornada inteira. Vamos começar com a solução de força bruta, construir os fundamentos combinatórios desde os primeiros princípios, derivar a fórmula ótima e implementá-la em Elixir. No final, você vai entender não só como resolver, mas por que a solução funciona.

O Problema

Você recebe dois inteiros, n e limit. É preciso distribuir todos os n doces entre 3 crianças de modo que nenhuma criança receba mais que limit doces. Retorne o número total de distribuições válidas.

Exemplos:

Input: n = 5, limit = 2
Output: 3
Explanation: As distribuições válidas são (1,2,2), (2,1,2), (2,2,1).

Input: n = 3, limit = 3
Output: 10
Explanation: Qualquer distribuição vale, já que nenhuma criança passa de 3.

Constraints:

• 1 <= n <= 10⁶
• 1 <= limit <= 10⁶

A assinatura em Elixir é:

defmodule Solution do
  @spec distribute_candies(n :: integer, limit :: integer) :: integer
  def distribute_candies(n, limit) do
    # implementação
  end
end

Passo 1: Pensando em Força Bruta — O Ponto de Partida

Meu primeiro instinto é sempre a abordagem mais simples possível: enumerar todas as possibilidades. Como são só 3 crianças, fixo a quantidade da primeira, depois a da segunda, e a terceira é o que sobrar.

Para cada valor possível de a (doces da criança 1):

• Sobram n - a doces.
• A criança 2 pode receber entre 0 e limit doces.
• A criança 3 recebe o restante, que também precisa estar entre 0 e limit.

Em Elixir, isso vira naturalmente uma comprehension:

defmodule Solution do
  def distribute_candies(n, limit) do
    for a <- 0..min(n, limit),
        b <- 0..min(n - a, limit),
        c = n - a - b,
        c >= 0 and c <= limit do
      {a, b, c}
    end
    |> length()
  end
end

Está correto e é fácil de entender. Mas a complexidade de tempo é O(n²) no pior caso — para n = 10⁶, seria lento demais. Precisamos de algo melhor.

É aqui que eu paro e pergunto: será que tem estrutura matemática aqui que eu estou perdendo?

Passo 2: Contando com Objetos Idênticos — Os Fundamentos

Antes de otimizar, precisamos entender o que estamos contando de verdade. Vamos tirar a programação da frente e pensar matematicamente.

A Pergunta Fundamental

Imagine 3 doces idênticos e 2 crianças distintas. De quantas formas dá para distribuir?

Enumerando:

• Criança A fica com 3, B com 0 → (3, 0)
• Criança A fica com 2, B com 1 → (2, 1)
• Criança A fica com 1, B com 2 → (1, 2)
• Criança A fica com 0, B com 3 → (0, 3)

São 4 formas. Note que os doces são idênticos (não dá para distinguir o doce #1 do #2), mas as crianças são distintas (dar 2 para Alice e 1 para Bob é diferente de dar 1 para Alice e 2 para Bob).

O Insight-Chave: Não É Sobre os Doces

Como os doces são idênticos, a única coisa que importa é quantos cada criança recebe. Então a pergunta "de quantas formas distribuir 3 doces para 2 crianças" é na verdade:

Quantos pares de inteiros não-negativos (a, b) satisfazem a + b = 3?

Resposta: 4 — (0,3), (1,2), (2,1), (3,0).

Essa tradução — de um problema físico de distribuição para um problema de equações — é o primeiro grande salto conceitual. É ela que permite trazer todo o poder da álgebra e da combinatória.

Passo 3: Stars and Bars — O Truque Visual

Codificando uma Distribuição como Desenho

Existe uma forma linda de visualizar distribuições. Represente cada doce como uma estrela ★ e use uma barra | para separar os grupos.

Para a + b + c = 5 (3 crianças), a distribuição (2, 1, 2) fica:

★★ | ★ | ★★

A distribuição (0, 5, 0) fica:

| ★★★★★ |

E (5, 0, 0) fica:

★★★★★ ||

A Tradução Mágica

Toda distribuição de n doces entre 3 crianças corresponde a exatamente um arranjo de:

• n estrelas (uma por doce)
• 2 barras (para criar 3 grupos)

E todo arranjo corresponde a exatamente uma distribuição. Isso é uma bijeção — correspondência um-para-um entre dois conjuntos aparentemente diferentes.

Ou seja: contar distribuições é o mesmo que contar arranjos de n estrelas e 2 barras!

Contando os Arranjos

De quantas formas arranjar n estrelas e 2 barras em fila? São n + 2 símbolos no total. Basta escolher quais 2 posições entre n + 2 vão ter as barras (o resto é estrela).

Isso é o coeficiente binomial:

C(n + 2, 2) = (n + 2)! / (2! × n!) = (n + 2)(n + 1) / 2

Para n = 3: C(5, 2) = 10. Conferindo, listando todas as distribuições de 3 doces para 3 crianças:

(0,0,3) (0,1,2) (0,2,1) (0,3,0)
(1,0,2) (1,1,1) (1,2,0)
(2,0,1) (2,1,0)
(3,0,0)

Exatamente 10! ✓

A Fórmula Geral

Para n doces e k crianças (sem limite), o número de distribuições é:

C(n + k - 1, k - 1)

Para k = 3: C(n + 2, 2). Essa é a fórmula de stars and bars.

A Intuição por Trás da Fórmula

Por que C(n + k - 1, k - 1)? Porque temos n estrelas e k - 1 barras (já que k grupos precisam de k - 1 separadores), totalizando n + k - 1 símbolos. Escolhemos quais k - 1 posições terão barras. As estrelas preenchem o resto.

Essa fórmula é uma das ferramentas mais importantes da combinatória. Aparece em todo lugar: distribuindo objetos idênticos, contando soluções inteiras não-negativas de equações lineares, até em teoria das probabilidades.

Passo 4: O Problema com Limites

Por Que Stars and Bars Não Basta

Nosso problema tem restrição: nenhuma criança pode receber mais que limit doces. Stars and bars conta todas as distribuições, incluindo as inválidas como (3, 1, 1), (4, 1, 0) e (5, 0, 0).

Por exemplo, com n = 5 e limit = 2, stars and bars dá C(7, 2) = 21 distribuições. Mas várias são inválidas.

Precisamos subtrair as inválidas. Mas com cuidado para não subtrair demais.

Passo 5: Inclusão-Exclusão — A Arte de Subtrair com Cuidado

A Ideia Central

Suponha que você quer contar elementos que não têm nenhuma de várias propriedades "ruins". O princípio da inclusão-exclusão diz:

|Válidos| = |Total|
          - |Ruim₁| - |Ruim₂| - |Ruim₃|
          + |Ruim₁ ∩ Ruim₂| + |Ruim₁ ∩ Ruim₃| + |Ruim₂ ∩ Ruim₃|
          - |Ruim₁ ∩ Ruim₂ ∩ Ruim₃|

Em palavras: subtraia cada caso ruim uma vez, some de volta os casos subtraídos duas vezes (porque têm duas propriedades ruins), subtraia os que têm três, e assim por diante.

A lógica é simples: quem tem exatamente uma propriedade ruim é subtraído uma vez (correto). Quem tem exatamente duas é subtraído duas vezes e somado de volta uma, saldo de uma subtração (correto). Quem tem três é subtraído três vezes, somado três, subtraído mais uma — saldo de uma (correto).

Aplicando ao Nosso Problema

Seja Ruim₁ o conjunto das distribuições onde a criança 1 recebe mais que limit. E assim por diante para Ruim₂ e Ruim₃.

Passo 1: Contar Ruim₁

Se a criança 1 passa do limite, dê a ela limit + 1 doces de cara. Sobram n - (limit + 1) = n - limit - 1 doces para distribuir livremente entre as 3 crianças.

Por stars and bars: C((n - limit - 1) + 2, 2) = C(n - limit + 1, 2).

Por simetria, |Ruim₂| = |Ruim₃| = |Ruim₁|. Então o total de "pelo menos uma criança estoura" é:

3 × C(n - limit + 1, 2)

Passo 2: Contar Ruim₁ ∩ Ruim₂

Se as crianças 1 e 2 estouram, dê limit + 1 para cada uma de cara. Sobram n - 2(limit + 1) = n - 2limit - 2 doces para distribuir livremente.

Por stars and bars: C(n - 2limit - 2 + 2, 2) = C(n - 2limit, 2).

Por simetria, são C(3, 2) = 3 pares desses:

3 × C(n - 2limit, 2)

Passo 3: Contar Ruim₁ ∩ Ruim₂ ∩ Ruim₃

Se as três estouram, dê limit + 1 para cada uma. Sobram n - 3(limit + 1) = n - 3limit - 3 doces.

Por stars and bars: C(n - 3limit - 3 + 2, 2) = C(n - 3limit - 1, 2).

Existe exatamente 1 terno desses:

C(n - 3limit - 1, 2)

A Fórmula Final

Juntando tudo:

Resposta = C(n + 2, 2)
         - 3 × C(n - limit + 1, 2)
         + 3 × C(n - 2limit, 2)
         - C(n - 3limit - 1, 2)

E como C(x, 2) = 0 quando x < 2 (não dá para escolher 2 itens de menos de 2), definimos:

C(x, 2) = x(x-1)/2   se x ≥ 2
        = 0           caso contrário

Isso nos dá uma solução O(1) em tempo e espaço!

Passo 6: Exemplo Trabalhado — n = 5, limit = 2

Vamos calcular cada termo:

Total (sem restrições):

C(5 + 2, 2) = C(7, 2) = 7 × 6 / 2 = 21

Uma criança estoura:

C(5 - 2 + 1, 2) = C(4, 2) = 4 × 3 / 2 = 6
3 × 6 = 18

Duas crianças estouram:

C(5 - 2×2, 2) = C(1, 2) = 0  (pois 1 < 2)
3 × 0 = 0

Três crianças estouram:

C(5 - 3×2 - 1, 2) = C(-2, 2) = 0  (pois -2 < 2)

Resposta:

21 - 18 + 0 - 0 = 3

Conferindo listando as distribuições válidas de 5 doces para 3 crianças com máximo 2 cada:

• (1, 2, 2) ✓
• (2, 1, 2) ✓
• (2, 2, 1) ✓

Exatamente 3! ✓

Passo 7: Implementação em Elixir — Inclusão-Exclusão

Agora traduzo isso para Elixir. O ponto-chave é um helper para a combinação que lida bem com argumentos negativos:

defmodule Solution do
  @spec distribute_candies(n :: integer, limit :: integer) :: integer
  def distribute_candies(n, limit) do
    total = comb(n + 2, 2)
    one_exceeds = 3 * comb(n - limit + 1, 2)
    two_exceed = 3 * comb(n - 2 * limit, 2)
    three_exceed = comb(n - 3 * limit - 1, 2)

    total - one_exceeds + two_exceed - three_exceed
  end

  # C(x, 2) = x * (x - 1) / 2, mas só se x >= 2
  defp comb(x, 2) when x >= 2 do
    div(x * (x - 1), 2)
  end

  defp comb(_x, _k), do: 0
end

Note o uso de div/2 para divisão inteira — o / do Elixir retorna float, o que quebraria a aritmética inteira com números grandes. A guard clause when x >= 2 cuida do caso em que o argumento da combinação é negativo ou pequeno demais.

Traçando n = 5, limit = 2:

• total = comb(7, 2) = div(7*6, 2) = 21
• one_exceeds = 3 * comb(4, 2) = 3 * div(4*3, 2) = 3 * 6 = 18
• two_exceed = 3 * comb(1, 2) = 3 * 0 = 0
• three_exceed = comb(-2, 2) = 0
• Resposta: 21 - 18 + 0 - 0 = 3 ✓

Passo 8: A Alternativa O(n) por Enumeração

Se inclusão-exclusão parece abstrata demais numa entrevista, existe uma abordagem O(n) mais simples que continua eficiente para n ≤ 10⁶.

A ideia é iterar sobre os valores possíveis para a primeira criança e, para cada valor, calcular de quantas formas dá para distribuir o restante entre as outras duas.

Para um a fixo (doces da criança 1):

• Restam: N = n - a
• A criança 2 precisa receber no mínimo max(0, N - limit) doces (para a criança 3 não estourar).
• A criança 2 pode receber no máximo min(N, limit) doces.
• A quantidade de valores válidos para a criança 2 é max(0, maxChild2 - minChild2 + 1).

defmodule Solution do
  def distribute_candies(n, limit) do
    min_child1 = max(0, n - 2 * limit)
    max_child1 = min(n, limit)

    if min_child1 > max_child1 do
      0
    else
      min_child1..max_child1
      |> Enum.reduce(0, fn a, acc ->
        remaining = n - a
        min_child2 = max(0, remaining - limit)
        max_child2 = min(remaining, limit)
        count = max(0, max_child2 - min_child2 + 1)
        acc + count
      end)
    end
  end
end

Bem mais intuitivo que inclusão-exclusão. É O(n) em tempo e O(1) em espaço, e é a abordagem que eu usaria se não tivesse segurança com a fórmula matemática na hora.

Por que funciona: fixar a criança 1 reduz o problema de 3 variáveis para 2, que se resolve em tempo constante por iteração. Essa técnica de "fixar uma variável" é uma estratégia universal que aparece em programação dinâmica e otimização combinatória.

Passo 9: Comparando as Abordagens

Para submissões no LeetCode, a solução por inclusão-exclusão é ideal porque é ótima em tempo e espaço. Mas a enumeração O(n) é um fallback perfeitamente aceitável, mais fácil de derivar e verificar.

O Modelo Mental — Resumo

O modelo mental que quero que você leve deste problema:

1. Reformule matematicamente: conte soluções inteiras não-negativas de a + b + c = n com cada variável ≤ limit.

2. Comece com força bruta: loops aninhados estão corretos, mas lentos.

3. Procure estrutura: reconheça a conexão com stars and bars. Toda distribuição corresponde a um arranjo de estrelas e barras.

4. Aplique inclusão-exclusão: subtraia casos inválidos, some de volta os contados duas vezes, subtraia os contados três vezes. Essa é a arte de subtrair com cuidado.

5. Traduza para Elixir: use guard clause para argumentos negativos da combinação, e div/2 para divisão inteira.

6. Verifique com exemplos: sempre trace os casos de teste dados.

7. Tenha um plano B: se a fórmula é difícil de derivar, a enumeração O(n) é segura e intuitiva.

Por Que Esse Problema Importa

O problema Distribute Candies Among Children II é mais que um desafio de código. É um microcosmo do campo inteiro da combinatória:

• Stars and bars ensina a ver distribuições como arranjos, convertendo um problema físico num problema de contagem.
• Inclusão-exclusão ensina a lidar com restrições contabilizando cuidadosamente overcounting e undercounting.
• Fixar variáveis ensina a reduzir problemas complexos a problemas mais simples, técnica que escala de 3 variáveis a 3 milhões.

Essas técnicas aparecem em todo lugar na computação: análise de algoritmos, teoria das probabilidades, machine learning, criptografia. Dominá-las num problema assim não é só passar num teste do LeetCode — é construir a intuição matemática que separa programadores competentes de excepcionais.

A beleza desse problema é que ele ensina a pensar matematicamente antes de codar. Em Elixir, a solução O(1) são quatro operações aritméticas e uma função helper — notavelmente concisa para um resultado tão poderoso. E essa concisão é a recompensa por entender a combinatória fundo o bastante para enxergar a fórmula escondida no problema.

Solução Completa

A solução final e ótima em Elixir:

defmodule Solution do
  @spec distribute_candies(n :: integer, limit :: integer) :: integer
  def distribute_candies(n, limit) do
    total = comb(n + 2, 2)
    one_exceeds = 3 * comb(n - limit + 1, 2)
    two_exceed = 3 * comb(n - 2 * limit, 2)
    three_exceed = comb(n - 3 * limit - 1, 2)

    total - one_exceeds + two_exceed - three_exceed
  end

  # C(x, 2) = x * (x - 1) / 2, mas só se x >= 2
  # Retorna 0 para argumentos negativos ou pequenos demais
  defp comb(x, 2) when x >= 2 do
    div(x * (x - 1), 2)
  end

  defp comb(_x, _k), do: 0
end

Essa solução roda em tempo O(1) e espaço O(1), lida com todos os edge cases e expressa o insight combinatório diretamente no código. É o ponto final de uma jornada que começou com loops aninhados e terminou com uma linha de aritmética — uma jornada que espelha como a maturidade matemática transforma a forma de programar.

Nota de verificação: todos os valores numéricos deste artigo (exemplo n = 5, limit = 2 → 3, listagem de stars-and-bars para n = 3, fórmula de inclusão-exclusão) foram checados por testes automatizados no projeto elixir_fundamentals (mix test: acordo total entre força bruta, fórmula e enumeração em todos os pares (n, limit) com n ≤ 12, mais concordância em escala com n = 10⁶).