Bir Tutam Algoritma Serisi Episode 1

Dun guzel bir algoritma sorusuyla karsilastim, hosuma gitti ve paylasmak istedim.

Soru temelinde bir matematik sorusu. Bir dongu dahi yazmadan O(1)’de cozulebiliyor. Basta sorunun algoritmik olarak nasil cozulebilecegine yogunlasip soruya matematiksel acidan yaklasmadim. Algoritmayi dusunurken kafam karisti fakat sonra matematiksel cozumu gorunce (itiraf ediyorum discussion’a bakmis bulundum), kodlamaya dalip matematik evreninden ne kadar kopmus oldugumun da farkina vardim. Guzel bir soru olmasinin yaninda hos bir intibaha da vesile oldu yani.

Sorunun linki;

https://www.hackerrank.com/challenges/strange-code/problem

Goruldugu gibi sorumuzda 3’ten baslamak uzere her seferinde 2’ye katlanacak sekilde 6,12,24… uzunluga sahip bloklarimiz var. Yani sayi dogrusunu 1-3’ten itibaren; 1-3,4-9,10-21,22-44…. Seklinde bolumlere ayiriyoruz. Her bolume karsilik gelen ve o bolumun uzunlugu kac ise (mesela 12 uzunluklu bolum olsun),o sayidan baslanip 1’e kadar azalan bir sayacimiz var. (12,11,10,…,1 seklinde). Bize input olarak bir sayi veriliyor, bu sayiya tekabul eden sayac degerini bulmamiz isteniyor. (Anlatimimin biraz flu olmus olabilir soru metnindeki aciklama gayet guzel, orayi da okumanizi oneririm.)

Cozume gecelim…

Ilk blokumuzun uzunlugu 3. 2.ninkisi 6, 3.nunki 12. Yani her blokun uzunlugu;

3 * (2^n)

Diyebiliriz. n sifirdan basliyor buna dikkat edelim.

Bir blokun uzunlugunu yazdik, peki o blokun baslangic degerini nasil bulacagiz? Daha onceki bloklarin uzunluklarinin toplami+1 dersek yanlis olmaz gibi… Yani n. blokun uzunlugu;

3 * (2^0) + 3 * (2^1) + 3 * (2^2) + … + 3 * (2^n-1)

seklindedir.

Bu ifadeyi matematiksel olarak kisaltmak mumkun. Hemen bir ornek uzerinden gosterelim. 3. bloku ele alalim. Bu blokun baslangic degeri ilk 2 blokun toplaminin bir fazlasi. Onceki bloklarin toplam uzunlugunu bulalim,

3 * (2^0) + 3 * (2^1)

Bu ifadeye bir tane 3*(2^0) ekleyip cikartalim;

3 * (2^0) + 3 * (2^1) + (3 * (2^0) - 3 * (2^0))

=

2 * 3 * (2^0) + 3 * (2^1) - 3 * (2^0)

=

3 * (2^1) + 3 * (2^1) - 3 * (2^0)

=

2 * 3 * (2^1) - 3 * (2^0)

=

3 * (2^2) - 3 * (2^0)

=

3 * (2^2 - 1)

Yani n.bloka kadar olan toplam uzunlugu,

3 * (2^n-1)

seklinde formule edebiliriz…

Bize input olarak verilen sayinin (x) hangi aralikta bulundugunu artik hesaplayabiliriz.

3 * (2^n-1) formulunde dikkat edilirse n degeri 1’den basliyor. Yani n=1 degerinde birinci blokun uzunlugunu 3 olarak elde ediyoruz. Dolayisiyla 3 * (2^n-1) ifadesi aslinda blogun baslangic degerini degil, bitis degerini vermekte… O halde input olarak aldigimiz sayimiz 3 * (2^n-1) ifadesine esit veya ondan kucuk olmali…

3 * (2^n-1) >= x

3 * (2^n-1) >= x

(2^n-1) >= x/3

2^n >= x/3+1

n >= log2( (x/3) +1 )

log2( (x/3) +1 ) ifadesinin ceil (tavan) degeri bize n’i verecek.

Input’un dahil oldugu blokun kacinci blok oldugunu bulduktan sonra problemi cozmek icin geriye bir kac basit matematik islemi kaliyor. Go dilinde yazilmis ornek kodu asagiya yapistiriyorum,

func strangeCounter(t int64) int64 {
    interval := math.Ceil(math.Log2(float64(t)/float64(3)+1))
    startValueOfInterval := 3*(math.Pow(2,interval-1)-1)+1
    return int64(3*math.Pow(2,interval-1) - (float64(t)-startValueOfInterval))
}

Herkese iyi gunler ve esenlikler dilerim…