İki haftada bir düzenlenen Leetcode yarışmasındaki üçüncü soruna bakalım 98 . Diğer yarışmalardan farklı problemlerin çözümlerini burada bulabilirsiniz .

Sorun Minimum İmkansız VEYA

Size 0 dizinli bir tamsayı dizisi verilir nums.

Bir x tamsayısının , bazı tamsayılar varsa , ifade edilebileceğini söylüyoruz . Başka bir deyişle, bir tamsayı, eğer bir altdizisinin bit düzeyinde VEYA'sı olarak yazılabiliyorsa ifade edilebilirdir .nums0 <= index1 < index2 < ... < indexk < nums.lengthnums[index1] | nums[index2] | ... | nums[indexk] = xnums

ile ifade edilemeyen minimum pozitif sıfır olmayan tamsayıyı döndürün .nums

Çözüm

Bu sorunun çözümünü anlamak için 0'dan 8'e kadar olan sayıları ve bunların ikili biçimde nasıl temsil edilebileceğini ve OR işlemi kullanılarak nasıl oluşturulabileceğini ele alalım.

1 oluşturabilir miyiz ? Hayır. OR işlemini kullanarak belirli bir dizindeki 1'i 0 olarak değiştiremeyiz. Birinci hariç tüm bitlerde birinci hariç tümü sıfır olan 1'den büyük sayı yoktur. 2 oluşturabilir miyiz ? Hayır. 1 ile aynıdır ancak ikinci bit için aynı mantık uygulanır. 3 oluşturabilir miyiz? Evet. 3, 1 veya 2 olarak oluşturulabilir. 4 oluşturabilir miyiz ? Hayır. 1 ile aynı, ancak mantık üçüncü bite uygulanır. 5 oluşturabilir miyiz ? Evet. 5, 4 VEYA 1 olarak oluşturulabilir. 6 , 4 VEYA 2'dir. 7 , 4'tür VEYA 2 VEYA 1. 8 oluşturulamaz. 1 ile aynı, ancak mantık dördüncü bite uygulanır. Bulunan alt diziyi genelleştirirsek:

• VEYA işlemi ile diğer sayılardan 2'nin kuvvetini oluşturamayız.
• 2'den N'ye kadar kuvvetlerimiz varsa, 2^N-1'e kadar diğer tüm sayıları oluşturabiliriz.

Yaklaşmak

İlk dizideki tüm sayıları HashSet'e taşıyoruz. Diziye ilk sunulana kadar 2'nin katlarını üreteceğiz.

İşte JavaScript çözümü:

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;
    }
}

Zaman karmaşıklığı: O(N)

Uzay karmaşıklığı: O(N)

PS

İşte Leetcode'daki çözümüm .