dua angka terakhir pemangkatan bilangan bulat

Berawal dari status kawan di facebook tentang tantangan kecil di hackerrank 2 minggu yang lalu. Akhirnya saya ikutan mencoba membuat program sederhana dengan python. Sebetulnya hanya iseng saja di sela-sela menulis.

Persoalannya adalah diberikan dua buah angka yaitu K dan N.  Hal yang ditanyakan adalah 2 angka terakhir dari deret S = 1^N + 2^N + … + K^N

Awalnya saya pakai bruteforce saja untuk ingin tahu test case-nya sejauh mana. Karena yang diinginkan hanyalah 2 digit terakhir maka bagian yang perlu dijumlahkan juga cukup 2 digit terakhir saja. Selain suku (term) yang dijumlahkan, bagian yang dipangkatkan juga cukup bagian yang berkontribusi pada 2 digit belakang saja. kode akhirnya bisa dilihat di potongan kode berikut ini:

if __name__=="__main__":
    T = int(raw_input().strip())
    for i in range(T):
        k, n = tuple([int(v) for v in raw_input().strip().split(" ")])
        sum = 1
        for x in range(2, k+1):
            xx = x % 100
            sum += (xx**n) % 100
        print "%.2d" % (sum % 100)

Kode di atas saya pakai Python versi 2. Ketika kode di atas dijalankan, ternyata ada 2 jenis pesan kesalahan yang muncul. Pertama adalah timeout dan yang kedua adalah MemoryError. Mari kita coba selesaikan satu per satu dimulai dari MemoryError.

Penyebabnya adalah fungsi range. Di Python 2, fungsi range akan menghasilkan objek list. Jika nilai k yang dimasukkan sangat besar maka akan ada banyak objek dialokasikan ke memori. Untuk kebutuhan pencacah iterasi seperti di atas, yang dibutuhkan hanya variabel yang nilainya menaik teratur. Ada fungsi lain yang bisa memenuhi kebutuhan ini yaitu xrange. Fungsi xrange akan menghasilkan objek generator sehingga memungkinkan iterasi dilakukan dengan continuation sehingga tidak perlu mengalokasikan banyak memori. Fungsi ini tidak ada lagi di Python versi 3 karena digabung dengan fungsi range.

Hal selanjutnya adalah masalah timeout. Tadinya saya pikir ini karena fungsi pemangkatannya tidak efisien. Saya berasumsi implementasi yang digunakan untuk pemangkatan adalah perkalian berulang sehingga akhirnya saya memutuskan untuk mengoptimasi bagian pemangkatan.

Ada beberapa cara mengoptimasi fungsi pangkat (power). Salah satunya adalah metode kuadrat. Metode ini memanfaatkan bentuk bilangan biner dari bilangan yang dijadikan pangkat. Fungsi ini ditulis secara rekursif sebagai berikut:

def _power(a, b):
    if b == 0:
        return 1
    else:
        temp = _power(a, b >> 1) % 100
        if b % 2 == 0:
            return temp*temp
        else:
            return a*temp*temp

Jadi pemangkatan dimulai dari bit paling belakang (bilangan bulat positif dipangkatkan 0 sama dengan 1). Kalau bit ini 0 (pangkat bilangan genap), maka basis dikuadratkan (pangkat 2). Perpindahan bit dalam bilangan biner berimplikasi pada proses perkalian/pembagian dengan 2.

Ternyata setelah bagian pemangkatan diganti dengan yang lebih cepat, programnya pun masih timeout. Kemudian saya berpikir keras. Setelah diamati angka hasil pemangkatan, ternyata ada pola berulang kemunculan angka terakhir. Misalnya, kalau angka terakhir bilangan yang dipangkatkan adalah 5 maka angka terakhir hasil pemangkatan akan terus 5. Contoh lainnya, kalau angka terakhir bilangan yang dipangkatkan adalah 3 maka angka terakhir hasil pemangkatan adalah berturut2 : 3, 9, 7, 1 (3, 9, 27, 81, 243, 729, …)

last_digit = [
    [0],
    [1],
    [2, 4, 8, 6],
    [3, 9, 7, 1],
    [4, 6],
    [5],
    [6],
    [7, 9, 3, 1],
    [8, 4, 2, 6],
    [9, 1]
    ]

Karena yang diminta di soal hanya 2 angka terakhir akhirnya saya coba mengamati pola untuk angka kedua dari belakang perihal ada tidaknya pola perulangan kemunculan angkanya dan memang ada! Hanya saja rentang perulangannya cukup besar yaitu 20 angka. Jadi, angka kedua dari belakang bilangan yang angka belakangnya x jika dipangkatkan p (p < 20) akan sama dengan jika dipangkatkan dengan p ditambah 20 dan kelipatannya (x*20+p). Akhirnya saya gunakan informasi ini untuk membuat pemangkatan yang hanya menghasilkan 2 angka terakhirnya saja. Tentunya setelah membuat tabel lookup sebanyak 101×21 (mempertimbangkan 0) angka.

def __power(k, n):
    px = k % 10
    pp = (n-1) % len(last_digit[px])
    dx = k % 100
    if n > 21:
        dn = n-22
        dn = 1+dn % 20
    else:
        dn = n-1
    return last_two[dx][dn]*10 + last_digit[px][pp]

Setelah kodenya diganti ternyata tetap saja timeout. Pusing juga. Akhirnya setelah makan saya coba iseng mengamati apakah kalau untuk dua buah nilai K (K1 dan K2) dan kedua bilangan tersebut memiliki selisih 100 apakah hasilnya sama atau tidak. Ternyata hasilnya berbeda, tetapi ada pola yang tak sengaja ketemu yaitu ternyata selisihnya berpola teratur. Kalau Selisih K2 dengan K1 adalah 100, maka nilai 2 angka terakhir K2 dipangkatkan N sama dengan 2 angka terakhir dari jumlah 100 dipangkatkan N dan K1 dipangkatkan N. Akhirnya programnya lolos tanpa timeout setelah diperbaiki.

def faul(k, n):
    sum = 0
    for x in xrange(1, k+1):
        xx = x % 100
        term = __power(xx, n)
        sum += term % 100
        sum %= 100
    return sum

def main():
    T = int(raw_input().strip())
    for i in xrange(T):
        k, n = tuple([int(v) for v in raw_input().strip().split(" ")])
        if k > 100:
            nk = k / 100
            pk = faul(100, n)
            print "%.2d" % ((nk*pk+faul(k%100, n))%100)
        else:
            print "%.2d" % faul(k, n)
        
if __name__=="__main__":
    main()

Ternyata (lagi), justru bagian inilah yang jadi kunci penyelesaian tanpa perlu menggunakan fungsi pangkat yang rumit-rumit. *tepokjidat*

Iklan