CP #38: Bit Manipulation Problemleri - 2

11. Majority Element

Problem surada.

Cozum

Ilk aklima gelen naive yontem, her bir elemanin arrayda kac kere gectigini tutan bir dictionary kullanmak. Daha sonra da, n/2'den fazla degeri olan key'i geri dondurmek. Ise yariyor ama iyilestirilebilir. 

def majorityElement(self, nums: List[int]) -> int:

    # biraz daha sekil olsun diye defaultdict yerine direk Counter kullanilabilir.

    counts = collections.Counter(nums)

    # ve de en fazla count degerine sahip elemani dondurebilirz.

    # cunku problemde majority degerinin var olacagi garanti ediliyor

    return max(counts.keys(), key=counts.get)

Baktigimizda, O(n) ile her bir elemani sayiyoruz. Toplamda O(n) time compl. ve de O(n) space compl. sahip bir cozum. 

Olaya baska bir acidan bakar isek, madem majority element, arraydaki toplam eleman sayisinin yarisindan fazla, bu array sort edilmis olsa idi kesinlikle en ortadaki eleman majority elemandan olurdu. Oyle ya, yarsindan fazlasini kapliyor arrayin. 

def majorityElement(self, nums: List[int]) -> int:

    nums.sort()

    return nums[len(nums) // 2]

Seklinde bir cozum elde etmis oluruz. Sorting icin O(nlogn) seklinde bir time compl. ve O(1) space compl. gerektigini gormekteyiz. Oncekine gore time compl. biraz daha kotu ama space compl. iyilesmis durumda. 

Follow-up sorusuna bakarsak, hep linear time hem de O(1) space compl. ile cozmemiz isteniyor. 

Peki, soyle dusunelim. Arrayi sort etmeden traverse ediyoruz. Ilk bastaki sayi, bizim adayimiz. Diger eleman eger adaya esit ise, count degerini bir artiriyoruz. Egere esit degilse bir azaltiyoruz. Bu durumda egere count degeri sifira tekrar ulasir ise, aday olan eleman, o ana kadar traverse edilmis olan arrayin yarisini kapliyor demektir. Yani henuz majority eleman degil. Su ornege bakalim:

1, 1, 2, 3

Adayimiz 1. Counter degerini 1 yaptik. Diger eleman yine 1, counter degerini 2 yaptik. Sonra gelen 2 eleman da 1 olmadiklari icin Counter degeri sifira dusmus oldu. Tam bu noktada, arrayin son bir elemani var ise, (ki olmak zorunda, cunku problmede, verilen input icerisinde bir majority eleman olacagi garanti ediliyor), o da 1 olmak zorundadir. Aslinda toplam tekrar sifira dustugu anda, yeni bir aday belirlemek icin elverisli noktadir. Bu ornekte, son eleman yine 1 olmak zorunda olacagi icin, yeni aday 1 olacaktir ve array sonuna gelindigi icin, majority eleman olarak 1 belirlenmis olacaktir. 

Implementasyona gecersek daha iyi anlasilabilir:

def majorityElement(self, nums: List[int]) -> int:

    # henuz bir adayimiz yok

    candidate = None

    count = 0

    for num in nums:

        # count degeri sifir iken, bir majority eleman henuz yok demektir.

        # bu durumda gelen ilk elemani, aday olarak belirleyebiliriz

        if count == 0:

            candidate = num

        # aday belirlendikten sonra, gelen eleman aday ile ayni ise

        # counter 1 artirilir

        # ayni degil ise 1 azaltilir. 

        count += (1 if num == candidate else -1)

    # iterasyon sonucunda elde kalan son candidate

    # majority eleman olacaktir

    return candidate

Analizina bakarsak, single pass ile verilen arrayi traverse ettik. Buradan O(n) time compl. geliyor. Diger taraftan da sadece counter degiskeni ekstra hafiza kapliyor, yani O(1) space compl. sahip bir cozum elde etmis olduk. 

Bu algoritma Boyer-Moore Voting Algorithm olarak gecmektedir. 

12. Bit Swap
Verilen bir binary sayi icin i ve j indexlerinde bulunan bitleri swap ediniz. Ornek: 101 sayisi icin i=0 ve j = 2 bitlerini swap ettigimizde: 

101 => 1100101 => 0110101 = 53

Sonucuna ulasilir. i ve j indexleri sol taraftan basladigina dikkat edelim.

Cozum

Oncelikle i ve j indexlerindeki bitler birbirinden farkli mi diye kontrol edebiliriz. Ne de olsa eger farkli degillerse, swap etmek birseyi degistirmeyecektir. 

Daha sonra naive bir cozum olarak i indexinde hangi deger var bir bitmask vasitasi ile bakilabilir. Bu sekilde i ve j indexlerindeki bit degerleri okunarak 2 farkli degiskende tutulur. Daha sonra da orjinal sayi uzerinde bunlari degeri caprazlama set edilerek sonuca ulasilir. 

def swap_bits(x, i, j):

    # i ve j indexleri soldan basladigi icin, 

    #  bit maski olusturmak icin kac bit sola shift edecegimiz

    # bit_len - i - 1 ile hesaplanir

    bit_len = x.bit_length()

    i_val = x & (1 << bit_len - i - 1)

    j_val = x & (1 << bit_len - j - 1)

    # eger i indexinde bir varsa, 

    # j indexindeki biti bire set edecegiz

    if i_val:

        x = x | (1 << bit_len - j - 1)

    else:

        # sifir varsa, j inexini sifira set edecegiz

        x = x & ~(1 << bit_len - j - 1)

    # ayni sekilde, j indexinde 1 biti var ise
    # i indexini 1'e set edelim

    if j_val:

        x = x | (1 << bit_len - i - 1)

    else:

        x = x & ~(1 << bin_len - i - 1)

    return x

O(1) time compl. ve O(1) space compl. ile cozmus olsak da, cok hos bir cozum olmadigi asikar. Nasil bit optimizasyon yapabiliriz? 

Sadece i ve j noktasindaki bitlerin degerleri farkli oldugu zaman swap yapmak anlamli olduguna gore ve ayrica bir bit anca 1 veya 0 degeri alabildigine gore, biz bu bitlerin degerinin tersini alsak zaten ayni sonuca ulasacagiz demektir. Yani i konumundaki biti okuyup j'ye set edip, j dekini okuyup i'ye set etmek yerine i ve j deki bitlerin degillerini alsak (flip etsek) ayni sonuca ulasiriz. 

Bir biti flap etmek icin, 1 ile XOR islemine sokabiliriz.

def swap_bits(x, i, j):

    bit_len = x.bit_length()

    

    # kolaylik olsun diye indexleri sagdan baslatalim

    i = 1 << bit_len - i - 1

    j = 1 << bit_len - j - 1

    # i ve j indexlerindeki bit degerleri farkli mi? 

    if x & 1 << i != x & 1 << j:

        # i noktasindaki biti flip edelim

        #x = x ^ (1 << i)

        # j noktasindaki biti flip edelim

        #x = x ^ (1 << j)

        # hatta bu ikisini birlestirebiliriz

        x ^= (1 << i) | (1 << j)

    return x

Daha kompakt ve ilmi bir cozum elde etmis olduk.

13. Reverse Bits

Verilen 64bitlik bir integer sayinin bitlerini reverse ediniz. 

Cozum

Bir yukaridaki problemde kullandigimiz bit swap yontemini kullanabiliriz. Boylece n bit varsa, n/2 adimda tum bitleri swap ederek, binary sayiyi reverse etmis oluruz. Toplamda O(n) time compl. tekabul etmektedir. 

Biraz daha iyilestirebiliriz. Binary basamaklar sadece 0 ve 1 den olustugu icin, ornegin 2 basamakli bir binary sayinin alabilecegi deger sadece 4 tanedir. 00, 01, 10 ve 11. Bu noktadan yola cikarak bir look-up table olusturabilir ve her bir 2 basamakli binary sayinin tersini bu tabloda tutabiliriz. Bu durumda O(1) time compl. ile her bir reverse islemini yapabiliriz. 

Verilen sayinin 64 bitlik oldugunu dusunursek, 16 basamakli binary sayilar icin bir lookup table yapabiliriz. (2^16 farkli sayiyi tabloda tutmak demek oluyor.) Verilen 64 bitlik binary sayiyi da 16 bitlik 4 gruba ayirirsak, reverse islemi soyle olacaktir:

[y3][y2][y1][y0] ==> [y'0][y'1][y'2][y'3] 

Yani her bir 16bitlik grubu ters cevirirken ayni zamanda siralamasini da ters cevirmemiz gerekiyor. Sadece ornegin y0'lik kismi nasil koparabiliriz? Tum sayiya x dersek, 

x & bitmask dedigimizde, y0'i koparabiliriz. y0'i sag tarafta en basa koymak icin de mask_size'in 3 kati kadar sola shift edebiliriz. y1'i koparmak icin ise, x'i mask_size kadar saga kaydirim (y0'dan kurtulup), ayni AND islemini uygulayabiliriz. Sag taraftada mask_size'in 2 kati kadar sola shift edip, onceki shift ettigimiz y0 ile OR islemine sokarak birlestirebiliriz. 

Cozumu toparlarsak,

def reverse_bits(x):

    mask_size = 16

    # verilen sayi icerisinden sadece 16 bit koparmak icin 

    # tum basamaklari 1 olan 16 bitlik bir bitmask tanimliyoruz

    bitmask = 0xFFFF 

    

    # lookup table'i REV seklinde adlandirdigimizi dusunelim

    return REV[x & bitmask] << (mask_size * 3) | \

               REV[(x >> mask_size) & bitmask] << (mask_size * 2) | \

               REV[(x >> (mask_size*2)) & bitmask] << mask_size | \

               REV[(x >> (mask_size*3)) & bitmask]

 

Bit sayisina n dersek, toplamda O(n/L) islem yaparak bitleri reverse etmis olduk. Burada L, mask_size olmaktadir. Lookup table'da 2^L adet sayi tuttugumuza gore de, O(2^L) space compl. var diyebiliriz. 

14. Find A Closest Integer With The Same Weight
Bir sayinin binary gosteriminde, sahip oldugu toplam 1 bit sayisi, sayigini agirligi (weight) olarak tanimlaniyor. Verilen bir x sayisi icin, ayni agirliga sahip olan ancak kendi degeri farkli olan, ayni zamanda degeri verilen x sayisina en yakin olan sayiyi bulunuz. Yani |y-x| minimum olacak.

Ornek: x=6 icin binary gosterim: 110. 

Agirligi ayni olan ve 6'ya en yakin olan sayi ise 5 tir, yani 101. 

Cozum

Ornekte de goruyoruz ki, agirligi degismeyecegi icin, yapabilecegimiz tek sey, bitleri swap etmek. Ama bunu yaparsak sayiyi olabildigince az degistirecegiz. Bu da demek oluyor ki, swaplar sag taraftan yapilmalidir. Cunku sola dogru gidildikce, basamak degeri arttigi icin, yapilaan swap islemi sayinin degerine cok fazla etki edecektir. 

Zaten ornekte de son 2 bit swap edilmis olarak goruluyor. Oysa ki ilk 2biti de swap ederek agirligi degistirmeden yeni bir sayi uretebilirdik. 110 -> 011. Bu durumda elde edecegimiz sayi 3 olacak. Ki bu da, 5 varken min(|y-x|) kosulunu saglamiyor. 

Ornekte sansli idik, son iki basamak 0 ve 1di ve swap etmek mantikli oluyordu. Peki ya son iki basamak 00 yada 11 ise? Bu durumda, yapacagimiz sey, en son basamktan baslayarak, farkli olan iki basamak bulup bunlari swap etmek olacaktir. Basamaklar bu arada arka arkaya olmalidir cunku swap edilen basamaklar arasinda da fak cok olursa, sayida yapilan degisiklik yuksek olacaktir.

def closest_int_same_weight(x):

    # sondan baslayarak yanyana 2 biti karsilastiriyoruz

    for i in range(1, x.bit_length()):

        if (x >> i) & 1 != (x >> i-1) & 1:

            # bitlerin degerlerini flip et ki, swap etmis gibi olalim

            x ^= 1 << i

            x ^= 1 << (i - 1)

            # hatta iki ifadeyi birlestirebiliriz

            # x ^= 1 << i | (1 << i-1)

            return x

    

    # buraya kadar gelip de arka arkaya olan ve degerleri farkli olan

    # 2 bit bulamadi isek, sayi tamamen 0dan ya da 1den olusuyor demektir.

    # ValueError raise edebiliriz.

    raise ValueError("sayi tamamen 1 veya 0'lardan olusamaz")

Gayet temiz O(n) time compl. bir cozum elde ettik. Ekstra memory kullanmadik, O(1) space compl.

Neler Ogrendik?

- Python'da counter kullanimi: Verilen bir arraydaki elemanlari saymak icin pratik bir yontem:

    # once collections'u import etmek gerekli

    import collections

    item_counts = collections.Counter([1,1,2,2,3,3,3]) => {1: 2, 2:2, 3:3}

    # string de bir array oldugu icin, karakterleri sayabiliriz

    char_counts = collections.Counter("lombak") => {'l': 1, 'o': 1, 'm': 1, 'b': 1, 'a': 1, 'k': 1}

    en yuksek count degerine sahip elemani su sekilde bulabiliriz:

    max(char_counts.keys(), key=char_counts.get)

    Burada char_counts dictionary oldugu icin once keys() ile tum karakterleri bir array olarak aliyoruz.     Max'i hesaplamak icin ise her bir karakterin value degerini char_counts.get metodu ile aliyoruz.

- Boyer-Moore Voting Algorithm: Majority elemanin O(n) ile bulunmasinda kullanilir. Arraydaki ilk eleman aday olacak sekilde baslanir, array itere edilirken, adaya rastlandiginda counter 1 artirilir. Adaydan farkli bir elemana rastlanirsa counter 1 azaltilir. Counter degeri sifira dustugu anda, gelen ilk eleman yeni aday olarak belirlenir. Iterasyon bittiginde, son aday, majority eleman olacaktir. 

- Binary'den integere donusum: int constructor'u taban degeri de alabilmektedir. Burada 2 verilerek, binary stringden int'e cevrilebilir.

    num = int("11010100", 2) 

- Herhangi bir bitiri sifira set etme: Verilen bir binary sayinin i. basamagini degeri ne olursa olsun sifira set emek icin, 1'in tersi ile AND islemine sokabiliriz. Bu durumda o basamak kesinlikle sifir olacaktir.

    x = x & ~(1 << i)

    Benzer sekilde degerinden bagimsiz olarak i. biti 1'e set etmek istersek de, 1 ile OR islemine sokabilriz:

    x = x | (1 << i)

- Binary stringing sadece belirli bir parcasini okuma: Oncelikle verilen binary sayi gerektigi kadar saga shift edilerek, okunacak kismin en sona gelmesi saglanir. Daha sonra okunacak kisim kadar uzunlukta olup tum bitleri 1 olan bir bitmask ile  AND islemine sokulur. Ornegin 64 bitlik bir sayidan, bastan 2. 16 bitlik kismi okumak istersek:

    x = [y0][y1][y2][y3] 

Once x'i saga 16*2 kere shift edip:

    x >> (16 * 2) = [y0][y1]

Daha sonra da 16 adet 1 bitten olusan bitmask ile AND'liyoruz:

    x & 0xFFFF => [y3]

----------------------------

Post yeterince uzadi arkadaslar. Diger problemlerle gorusmek uzere. 

Bol problemli gunler diliyorum.

Stay hungry, stay foolish, stay healthy :)