Diamo un'occhiata al terzo problema del concorso bisettimanale Leetcode 98 . Puoi trovare soluzioni di diversi problemi da altri concorsi qui .

Problema Minimo Impossibile OR

Ti viene fornito un array di numeri interi con indice 0nums .

Diciamo che un intero x è esprimibile da numsse esistono degli interi 0 <= index1 < index2 < ... < indexk < nums.lengthper i quali nums[index1] | nums[index2] | ... | nums[indexk] = x. In altre parole, un numero intero è esprimibile se può essere scritto come OR bit a bit di una sottosequenza di nums.

Restituisce il numero intero positivo minimo diverso da zero che non è esprimibile danums .

Soluzione

Per comprendere la soluzione a questo problema, consideriamo i numeri da 0 a 8 e come potrebbero essere rappresentati in formato binario e formati utilizzando l'operazione OR.

Possiamo formare 1 ? No. Non possiamo cambiare 1 in un particolare indice in 0 usando l'operazione OR. Non esiste un numero maggiore di 1 con tutti zeri tranne il primo in tutti i bit tranne il primo. Possiamo formare 2 ? No. Come per 1 ma la stessa logica viene applicata al secondo bit. Possiamo formare 3? SÌ. 3 potrebbe essere formato come 1 OR 2. Possiamo formare 4 ? No. Come per 1 ma la logica viene applicata al terzo bit. Possiamo formare 5 ? SÌ. 5 potrebbe essere formato come 4 OPPURE 1. 6 è 4 OPPURE 2. 7 è 4 OPPURE 2 OPPURE 1. 8 non può essere formato. Come per 1 ma la logica viene applicata al quarto bit. Se generalizziamo la sottosequenza trovata:

• Non possiamo formare una potenza di 2 da nessun altro numero con l'operazione OR.
• Se abbiamo potenze da 2 fino a N, possiamo formare tutti gli altri numeri fino a 2^N-1

Approccio

Spostiamo tutti i numeri dall'array iniziale in HashSet. Genereremo potenze di 2 fino al primo non presentato nell'array.

Ecco la soluzione 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;
    }
}

Complessità temporale: O(N)

Complessità spaziale: O(N)

PS

Ecco la mia soluzione su Leetcode .