Palindrom Problemi ve Bit

Arşivden çıkan bir başka probleme bakalım.

Soru metnini yine tam hatırlayamıyorum ancak aşağıdakine benzerdi.

Oyun-sever alex bir string oluşturuyor.

Önce alfebenin ilk harfini yazıyor. Sıradaki harfi yazdıktan sonra o harfe kadar yazdıklarının palindromunu metnin sonuna ekliyor.

Alex a harfini yazdı ve sıradaki harfi yazdıktan sonra önceki kısmın palindromunu ekledi.

aba

İşlemi tekrarlayalım.

abacaba
abacabadabacaba
abacabadabacabadabacabadabacaba

bu işlemi alfabedeki tüm harfler bitinceye kadar tekrarlıyor.

Bizden istenen input olarak verilen bir positif tamsayı n için metnin n. elemanını bulmak. 1 <= N < 2^27

Çözüm

Problemi ağaç şeklinde ifade edersek root eleman z karakteri olur. z karakteri 2 tane y node u içerir. her bir y node u 2 şer tane x içerir. Bu şekilde leaf nodeların hepsi a karakteri olur.

Eğer dikkatlice incelersek

• 1. karakter a
• 2. karakter b
• 4. karakter c
• 8. karakter d
• .
• .
• .
• 2^26. karakter z

Problemimiz şuna dönüştü. Input değeri binary olarak ifade edip right most set bitin karşılık geldiği indexi bulduğumuzda, alfabedeki indexinci karakter bize metindeki n. karakteri verir.

Böylelikle problemi O(Bit Count) zamanda çözebildik. Bit işlemleri genellikle hardware seviyesinde desteklendiği bunları yapabilecek cpu instructionlara sahip oluyor. Bunu bildiğimize göre O(1) zamanda çözülmüştür diyebiliriz.

1
2
3
4
5
6
7

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N = 350;
    printf("%c\n", (char)(96 + ffs(N));
}