problems - lcm algorithm




A questão da entrevista fácil ficou mais difícil: dados números 1..100, encontre o(s) número(s) faltante(s) (20)

Aqui está um resumo do link de Dimitris Andreou .

Lembre-se da soma dos i-és poderes, onde i = 1,2, .., k. Isso reduz o problema para resolver o sistema de equações

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Usando as identidades de Newton , sabendo que eu posso computar

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Se você expandir o polinômio (xa 1 ) ... (xa k ) os coeficientes serão exatamente c 1 , ..., c k - veja as fórmulas de Viète . Como todos os fatores polinomiais são únicos (o anel de polinômios é um domínio euclidiano ), isso significa que os i são determinados unicamente até a permutação.

Isso termina com uma prova de que lembrar poderes é o suficiente para recuperar os números. Para k constante, essa é uma boa abordagem.

No entanto, quando k está variando, a abordagem direta de calcular c 1 , ..., c k é proibitivamente cara, pois, por exemplo, c k é o produto de todos os números faltantes, magnitude n! / (Nk) !. Para superar isto, execute cálculos no campo Z q , onde q é um primo tal que n <= q <2n - existe pelo postulado de Bertrand . A prova não precisa ser alterada, pois as fórmulas ainda são válidas e a fatoração de polinômios ainda é única. Você também precisa de um algoritmo para fatoração sobre campos finitos, por exemplo, o de Berlekamp ou Cantor-Zassenhaus .

Pseudocódigo de alto nível para constante k:

  • Calcule i-és poderes de números dados
  • Subtraia para obter somas do i-ésimo poder de números desconhecidos. Ligue para as somas b i .
  • Use as identidades de Newton para calcular os coeficientes de b i ; chame-os c i . Basicamente, c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 ) / 2; veja Wikipedia para fórmulas exatas
  • Fator o polinômio xk- c 1 x k-1 + ... + c k .
  • As raízes do polinômio são os números necessários a 1 , ..., a k .

Para variar k, encontre um primo n <= q <2n usando, por exemplo, Miller-Rabin, e execute os passos com todos os números reduzindo o módulo q.

EDIT: A versão anterior desta resposta afirmou que, em vez de Z q , onde q é primo, é possível usar um campo finito de característica 2 (q = 2 ^ (log n)). Este não é o caso, uma vez que as fórmulas de Newton requerem divisão por números até k.

Eu tive uma interessante experiência de entrevista de emprego há algum tempo. A questão começou muito fácil:

Q1 : Temos uma bolsa contendo números 1 , 2 , 3 ,…, 100 . Cada número aparece exatamente uma vez, portanto, há 100 números. Agora um número é escolhido aleatoriamente da sacola. Encontre o número que falta.

Eu ouvi essa pergunta da entrevista antes, claro, então eu respondi rapidamente ao longo das linhas de:

A1 : Bem, a soma dos números 1 + 2 + 3 + … + N é (N+1)(N/2) (ver Wikipedia: soma das séries aritméticas ). Para N = 100 , a soma é 5050 .

Assim, se todos os números estiverem presentes no saco, a soma será exatamente 5050 . Como um número está faltando, a soma será menor que isso, e a diferença é esse número. Assim, podemos encontrar o número que falta no tempo O(N) e no espaço O(1) .

Nesse ponto, achei que tinha ido bem, mas de repente a pergunta deu uma guinada inesperada:

Q2 : Isso está correto, mas agora como você faria isso se dois números estão faltando?

Eu nunca tinha visto / ouvido / considerado essa variação antes, então entrei em pânico e não pude responder à pergunta. O entrevistador insistiu em conhecer o meu processo de pensamento, então eu mencionei que talvez possamos obter mais informações comparando com o produto esperado, ou talvez fazendo um segundo passe depois de ter reunido algumas informações do primeiro passe, etc, mas eu realmente estava apenas atirando no escuro, em vez de realmente ter um caminho claro para a solução.

O entrevistador tentou me encorajar dizendo que ter uma segunda equação é de fato uma maneira de resolver o problema. Neste ponto eu fiquei meio chateado (por não saber a resposta antes da mão), e perguntei se esta é uma técnica de programação geral (leia-se: "útil"), ou se é apenas uma resposta de truque / pegadinha.

A resposta do entrevistador me surpreendeu: você pode generalizar a técnica para encontrar 3 números ausentes. Na verdade, você pode generalizá-lo para encontrar os números que faltam.

Qk : Se exatamente k números estão faltando na bolsa, como você vai encontrá-lo de forma eficiente?

Isso foi há alguns meses e ainda não consegui descobrir o que é essa técnica. Obviamente, existe um limite inferior de Ω(N) , já que devemos varrer todos os números pelo menos uma vez, mas o entrevistador insistiu que a complexidade de TEMPO e ESPAÇO da técnica de resolução (menos a varredura de entrada de tempo O(N) ) é definida em k não N.

Então a questão aqui é simples:

  • Como você resolveria o Q2 ?
  • Como você resolveria o Q3 ?
  • Como você resolveria Qk ?

Esclarecimentos

  • Geralmente existem N números de 1 .. N , não apenas 1..100.
  • Eu não estou olhando para a solução óbvia baseada em conjunto, por exemplo, usando um conjunto de bits , codificando a presença / ausência de cada número pelo valor de um bit designado, portanto, usando O(N) bits no espaço adicional. Não podemos arcar com nenhum espaço adicional proporcional ao N.
  • Eu também não estou procurando pela óbvia abordagem de ordenação inicial. Esta e a abordagem baseada em conjuntos merecem ser mencionadas numa entrevista (são fáceis de implementar e, dependendo do N , podem ser muito práticas). Eu estou procurando a solução do Santo Graal (que pode ou não ser prática de implementar, mas tem as características assintóticas desejadas).

Então, novamente, é claro que você deve escanear a entrada em O(N) , mas você só pode capturar uma pequena quantidade de informação (definida em termos de k não N ), e então encontrar os k números que faltam de alguma forma.


Aqui está uma solução que usa k bits de armazenamento extra, sem truques inteligentes e simples. Tempo de execução O (n), espaço extra O (k). Apenas para provar que isso pode ser resolvido sem antes ler a solução ou ser um gênio:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Espere um minuto. Como a pergunta é declarada, existem 100 números na bolsa. Não importa quão grande seja, o problema pode ser resolvido em tempo constante, porque você pode usar um conjunto e remover números do conjunto em no máximo 100 k iterações de um loop. 100 é constante. O conjunto de números restantes é sua resposta.

Se generalizarmos a solução para os números de 1 a N, nada muda, exceto que N não é uma constante, então estamos no tempo O (N - k) = O (N). Por exemplo, se usarmos um bit set, definimos os bits para 1 em O (N) time, iteramos os números, definimos os bits como 0 à medida que vamos (O (Nk) = O (N)) e então tem a resposta.

Parece-me que o entrevistador estava perguntando a você como imprimir o conteúdo do conjunto final no tempo O (k) ao invés do tempo O (N). Claramente, com um pouco definido, você tem que percorrer todos os N bits para determinar se você deve imprimir o número ou não. No entanto, se você alterar a maneira como o conjunto é implementado, poderá imprimir os números em k iterações. Isso é feito colocando os números em um objeto para serem armazenados em um conjunto de hash e em uma lista duplamente vinculada. Quando você remove um objeto do conjunto de hash, também o remove da lista. As respostas serão deixadas na lista que é agora de comprimento k.


Eu não chequei a matemática, mas eu suspeito que computação Σ(n^2) na mesma passagem que nós calculamos Σ(n) forneceria informação suficiente para obter dois números perdidos, Do Σ(n^3) também se existem três e assim por diante.


Não tenho certeza, se é a solução mais eficiente, mas eu faria um loop em todas as entradas, e usaria um bitset para lembrar, quais números são definidos e, em seguida, teste para 0 bits.

Eu gosto de soluções simples - e eu até acredito que pode ser mais rápido do que calcular a soma ou a soma dos quadrados etc.


O problema com soluções baseadas em somas de números é que elas não levam em conta o custo de armazenar e trabalhar com números com grandes expoentes ... na prática, para trabalhar para números muito grandes, uma biblioteca de números grandes seria usada . Podemos analisar a utilização do espaço para esses algoritmos.

Podemos analisar a complexidade temporal e espacial dos algoritmos do sdcvvc e Dimitris Andreou.

Armazenamento:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Então, l_j \in \Theta(j log n)

Armazenamento total utilizado: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Espaço usado: assumindo que calcular a^j leva ceil(log_2 j) tempo, tempo total:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Tempo total usado: \Theta(kn log n)

Se esse tempo e espaço forem satisfatórios, você poderá usar um algoritmo recursivo simples. Seja b i a entrada na bolsa, n o número de números antes das remoções e k o número de remoções. Na sintaxe de Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Armazenamento usado: O(k) para lista, O(log(n)) para pilha: O(k + log(n)) Esse algoritmo é mais intuitivo, tem a mesma complexidade de tempo e usa menos espaço.


Podemos resolver Q2 somando os números em si e os quadrados dos números.

Podemos então reduzir o problema para

k1 + k2 = x
k1^2 + k2^2 = y

Onde x e y são quanto as somas estão abaixo dos valores esperados.

Substituir nos dá:

(x-k2)^2 + k2^2 = y

O que podemos resolver para determinar nossos números ausentes.


Você vai encontrá-lo lendo o par de páginas de link . Mostra exatamente a generalização que você está procurando . Provavelmente é isso que o entrevistador leu e por que ele fez essas perguntas.

Agora, se apenas as pessoas começassem a deletar as respostas que são subsumidas ou substituídas pelo tratamento de Muthukrishnan, e tornem este texto mais fácil de encontrar. :)

Veja também sdcvvc's resposta diretamente relacionada sdcvvc's , que também inclui o pseudocódigo (não é necessário ler essas fórmulas matemáticas complicadas :)) (obrigado, ótimo trabalho!).


Eu acho que isso pode ser generalizado assim:

Denote S, M como os valores iniciais para a soma das séries aritméticas e multiplicação.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Eu deveria pensar em uma fórmula para calcular isso, mas esse não é o ponto. De qualquer forma, se um número estiver faltando, você já forneceu a solução. No entanto, se dois números estiverem faltando, vamos indicar a nova soma e o total múltiplo por S1 e M1, que serão os seguintes:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Como você sabe S1, M1, M e S, a equação acima é solucionável para encontrar a e b, os números que faltam.

Agora, para os três números que faltam:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Agora, o seu desconhecido é 3, enquanto você só tem duas equações que você pode resolver.


Isso pode parecer estúpido, mas, no primeiro problema apresentado a você, você teria que ver todos os números restantes na bolsa para realmente adicioná-los para encontrar o número que faltava usando essa equação.

Então, desde que você consiga ver todos os números, basta procurar o número que está faltando. O mesmo acontece quando dois números estão faltando. Bem simples eu acho. Não adianta usar uma equação quando você consegue ver os números restantes na sacola.


Para o Q2, essa é uma solução um pouco mais ineficiente que as outras, mas ainda tem tempo de execução O (N) e ocupa o espaço O (k).

A ideia é executar o algoritmo original duas vezes. No primeiro, você obtém um número total que está faltando, o que lhe dá um limite superior dos números que faltam. Vamos ligar para esse número N. Você sabe que os dois números que faltam vão se resumir N, então o primeiro número só pode estar no intervalo, [1, floor((N-1)/2)]enquanto o segundo vai estar dentro [floor(N/2)+1,N-1].

Assim, você liga todos os números novamente, descartando todos os números que não estão incluídos no primeiro intervalo. Os que são, você acompanha a soma deles. Finalmente, você conhecerá um dos dois números que faltam e, por extensão, o segundo.

Tenho a sensação de que esse método poderia ser generalizado e talvez várias pesquisas sejam executadas em "paralelo" durante uma única passagem sobre a entrada, mas ainda não descobri como.


Pode ser que este algoritmo possa funcionar para a pergunta 1:

  1. Precompute xor dos primeiros 100 inteiros (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. xor os elementos como eles continuam vindo do fluxo de entrada (val1 = val1 ^ next_input)
  3. resposta final = val ^ val1

Ou melhor ainda:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Esse algoritmo pode, de fato, ser expandido para dois números ausentes. O primeiro passo continua o mesmo. Quando chamamos GetValue com dois números ausentes, o resultado será um a1^a2dos dois números ausentes. Digamos

val = a1^a2

Agora para peneirar a1 e a2 do val, pegamos qualquer bit em val. Vamos dizer que o ithbit está definido em val. Isso significa que a1 e a2 têm paridade diferente na ithposição do bit. Agora fazemos outra iteração na matriz original e mantemos dois valores xor. Um para os números que possuem o ith bit set e outro que não possui o ith bit set. Agora temos dois baldes de números, e seus garantidos a1 and a2ficarão em diferentes baldes. Agora repita o mesmo que fizemos para encontrar um elemento ausente em cada um dos baldes.


Uma solução possível:

public class MissingNumber {
    public static void main(String[] args) {
        // 0-20
        int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
        printMissingNumbers(a,20);
    }

    public static void printMissingNumbers(int [] a, int upperLimit){
        int b [] = new int[upperLimit];
        for(int i = 0; i < a.length; i++){
            b[a[i]] = 1;
        }
        for(int k = 0; k < upperLimit; k++){
            if(b[k] == 0)
                System.out.println(k);
        }
    }
}

Você pode resolver o Q2 se tiver a soma das duas listas e o produto de ambas as listas.

(l1 é o original, l2 é a lista modificada)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Podemos otimizar isso já que a soma de uma série aritmética é n vezes a média do primeiro e do último termos:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Agora sabemos que (se aeb são os números removidos):

a + b = d
a * b = m

Então podemos reorganizar para:

a = s - b
b * (s - b) = m

E multiplique:

-b^2 + s*b = m

E reorganize de modo que o lado direito seja zero:

-b^2 + s*b - m = 0

Então podemos resolver com a fórmula quadrática:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Exemplo de código do Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Eu não sei a complexidade das funções sqrt, reduce e sum, então não posso resolver a complexidade desta solução (se alguém souber, por favor, comente abaixo).


Eu acho que isso pode ser feito sem quaisquer equações e teorias matemáticas complexas. Abaixo está uma proposta para uma solução de complexidade de tempo in-loco e O (2n):

Premissas da forma de entrada:

# de números em bag = n

Número de números ausentes = k

Os números no saco são representados por uma matriz de comprimento n

Comprimento da matriz de entrada para o algoritmo = n

Entradas ausentes na matriz (números retirados da bolsa) são substituídas pelo valor do primeiro elemento na matriz.

Por exemplo. Inicialmente a bolsa parece com [2,9,3,7,8,6,4,5,1,10]. Se 4 for retirado, o valor de 4 será 2 (o primeiro elemento da matriz). Portanto, depois de tirar 4 a sacola ficará como [2,9,3,7,8,6,2,5,1,10]

A chave para essa solução é marcar o ÍNDICE de um número visitado negando o valor nesse ÍNDICE conforme o array é percorrido.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

Eu acredito que eu tenho um algoritmo de O(k)tempo e O(log(k))espaço, dado que você tem as funções floor(x)e log2(x)para inteiros arbitrariamente grandes disponíveis:

Você tem um kinteiro longo -bit (daí o log8(k)espaço), onde você adiciona o x^2, onde x é o próximo número que você encontra no saco: s=1^2+2^2+...Isso leva O(N)tempo (o que não é um problema para o entrevistador). No final você obtém j=floor(log2(s))qual é o maior número que você está procurando. Então s=sje você faz novamente o acima:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Agora, você normalmente não tem funções floor e log2 para 2756inteiros de bits, mas sim para duplas. Assim? Simplesmente, para cada 2 bytes (ou 1, ou 3, ou 4) você pode usar essas funções para obter os números desejados, mas isso adiciona um O(N)fator à complexidade do tempo


Existe uma maneira geral de generalizar algoritmos de streaming como este. A idéia é usar um pouco de aleatorização para, esperançosamente, 'espalhar' os kelementos em sub-problemas independentes, onde nosso algoritmo original resolve o problema para nós. Essa técnica é usada na reconstrução de sinais esparsos, entre outras coisas.

  • Faça uma matriz ade tamanho u = k^2.
  • Escolha qualquer função hash universal , h : {1,...,n} -> {1,...,u}. (Como multiply-shift )
  • Para cada um iem 1, ..., naumentoa[h(i)] += i
  • Para cada número xno fluxo de entrada, decrementar a[h(x)] -= x.

Se todos os números ausentes tiverem sido divididos em hash em diferentes intervalos, os elementos diferentes de zero da matriz agora conterão os números ausentes.

A probabilidade de um par específico ser enviado para o mesmo intervalo é menor que a 1/udefinição de uma função hash universal. Como há cerca de k^2/2pares, temos que a probabilidade de erro é no máximo k^2/2/u=1/2. Ou seja, conseguimos com probabilidade pelo menos 50% e, se aumentarmos u, aumentamos nossas chances.

Observe que esse algoritmo toma k^2 lognbits de espaço (precisamos de lognbits por array bucket.) Isso corresponde ao espaço exigido pela resposta de @Dimitris Andreou (Em particular, o requisito de espaço de fatoração polinomial, que também é aleatório). tempo por atualização, em vez de tempo, kno caso de somas de energia.

De fato, podemos ser ainda mais eficientes do que o método da soma de potência usando o truque descrito nos comentários.


Nós podemos fazer o Q1 e Q2 em O (log n) a maior parte do tempo.

Suponha que nosso memory chipconsiste em uma série de nnúmeros de test tubes. E um número xno tubo de ensaio é representado por x milliliterlíquido químico.

Suponha que nosso processador seja um laser light. Quando acendemos o laser, ele percorre todos os tubos perpendicularmente ao seu comprimento. Toda vez que passa pelo líquido químico, a luminosidade é reduzida 1. E passando a luz em determinada marca de mililitro é uma operação de O(1).

Agora, se acendermos o nosso laser no meio do tubo de ensaio e obtermos a saída de luminosidade

  • é igual a um valor pré-calculado (calculado quando não há números faltando), então os números ausentes são maiores que n/2.
  • Se nossa saída for menor, haverá pelo menos um número ausente menor que n/2. Também podemos verificar se a luminosidade é reduzida por 1ou 2. se for reduzido, 1então um número em falta é menor do que n/2e outro é maior que n/2. Se for reduzido, 2então ambos os números são menores que n/2.

Podemos repetir o processo acima novamente e novamente estreitando nosso domínio de problema. Em cada etapa, reduzimos o domínio pela metade. E finalmente podemos chegar ao nosso resultado.

Algoritmos paralelos que valem a pena mencionar (porque são interessantes),

  • ordenando por algum algoritmo paralelo, por exemplo, a fusão paralela pode ser feita a O(log^3 n)tempo. E então o número que falta pode ser encontrado pela pesquisa binária no O(log n)tempo.
  • Teoricamente, se tivermos nprocessadores, cada processo poderá verificar uma das entradas e definir um sinalizador que identifique o número (convenientemente em uma matriz). E na próxima etapa, cada processo pode verificar cada sinalizador e, finalmente, exibir o número que não está sinalizado. Todo o processo levará O(1)tempo. Tem O(n)espaço adicional / exigência de memória.

Note que os dois algoritmos paralelos fornecidos acima podem precisar de espaço adicional como mencionado no comentário .


Você pode motivar a solução pensando nisso em termos de simetria (grupos, em linguagem matemática). Não importa a ordem do conjunto de números, a resposta deve ser a mesma. Se você for usar kfunções para ajudar a determinar os elementos ausentes, você deve estar pensando sobre quais funções têm essa propriedade: simétrica. A função s_1(x) = x_1 + x_2 + ... + x_né um exemplo de uma função simétrica, mas existem outras de maior grau. Em particular, considere as funções simétricas elementares . A função simétrica elementar do grau 2 é s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_na soma de todos os produtos de dois elementos. Da mesma forma para as funções simétricas elementares de grau 3 e superior. Eles são obviamente simétricos. Além disso, verifica-se que eles são os blocos de construção para todas as funções simétricas.

Você pode construir as funções simétricas elementares conforme avança observando isso s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Mais pensamento deve convencê-lo s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))e assim por diante, para que eles possam ser computados em uma única passagem.

Como podemos saber quais itens estão faltando na matriz? Pense no polinômio (z-x_1)(z-x_2)...(z-x_n). Ele avalia 0se você colocar qualquer um dos números x_i. Expandindo o polinômio, você consegue z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. As funções simétricas elementares aparecem aqui também, o que realmente não é surpresa, uma vez que o polinômio deve permanecer o mesmo se aplicarmos qualquer permutação às raízes.

Assim, podemos construir o polinômio e tentar fatorá-lo para descobrir quais números não estão no conjunto, como outros mencionaram.

Finalmente, se estamos preocupados com o transbordamento de memória com números grandes (o enésimo polinômio simétrico será da ordem 100!), podemos fazer esses cálculos mod ponde pé um primo maior que 100. Nesse caso, avaliamos o polinômio mod pe descobrimos que ele avalia novamente para 0quando a entrada é um número no conjunto e é avaliada como um valor diferente de zero quando a entrada é um número que não está no conjunto. No entanto, como outros apontaram, para obter os valores do polinômio no tempo que depende k, não N, temos que fatorar o polinômio mod p.


Você pode verificar se todos os números existem? Se sim, você pode tentar isto:

S = soma de todos os números no saco (S <5050)
Z = soma dos números que faltam 5050 - S

se os números que faltam são xe yentão:

x = Z - y e
max (x) = Z - 1

Então você verifica o intervalo de e 1para max(x)encontrar o número





math