Vejamos o terceiro problema do concurso quinzenal Leetcode 98 . Você pode encontrar soluções para diferentes problemas de outros concursos aqui .

Problema Mínimo Impossível OU

Você recebe um array inteiro indexado por 0nums .

Dizemos que um inteiro x é exprimível de numsse existem alguns inteiros 0 <= index1 < index2 < ... < indexk < nums.lengthpara os quais nums[index1] | nums[index2] | ... | nums[indexk] = x. Em outras palavras, um número inteiro pode ser expresso se puder ser escrito como OR bit a bit de alguma subsequência de nums.

Retorne o mínimo inteiro positivo diferente de zero que não pode ser expresso denums .

Solução

Para entender a solução desse problema, vamos considerar os números de 0 a 8 e como eles podem ser representados no formato binário e formados usando a operação OR.

Podemos formar 1 ? Não. Não podemos mudar 1 em um determinado índice para 0 usando a operação OR. Não há número maior que 1 tendo todos os zeros, exceto o primeiro em todos os bits, exceto o primeiro. Podemos formar 2 ? Não. O mesmo que para 1, mas a mesma lógica é aplicada ao segundo bit. Podemos formar 3? Sim. 3 poderia ser formado como 1 OU 2. Podemos formar 4 ? Não. O mesmo que para 1, mas a lógica é aplicada ao terceiro bit. Podemos formar 5 ? Sim. 5 pode ser formado como 4 OU 1. 6 é 4 OU 2. 7 é 4 OU 2 OU 1. 8 não pode ser formado. O mesmo que para 1, mas a lógica é aplicada ao quarto bit. Se generalizarmos a subsequência encontrada:

• Não podemos formar uma potência de 2 a partir de nenhum outro número com a operação OU.
• Se tivermos potências de 2 até N, podemos formar todos os outros números até 2^N-1

Abordagem

Movemos todos os números da matriz inicial para o HashSet. Iremos gerar potências de 2 até que o primeiro não seja apresentado no array.

Aqui está a solução JavaScript:

var minImpossibleOR = function(nums) {
    let set = new Set(nums);
    
    for (let i = 0; i <= 32; i++){
        let num = Math.pow(2, i)
        if(!set.has(num)){
            return num
        }
    }

    return -1;
};

impl Solution {
    pub fn min_impossible_or(nums: Vec<i32>) -> i32 {
        let mut set = std::collections::HashSet::new();
        for num in nums.iter() {
            set.insert(num);
        }
        
        for n in 0..=32 {
            let num:i32 = 2i32.pow(n);
            if(!set.contains(&num)){
                return num;
            }
        }
        return -1;
    }
}

Complexidade de tempo: O(N)

Complexidade do espaço: O(N)

PS

Aqui está minha solução em Leetcode .