Problem 4 - Largest Palindrome Product

Soru

Palindrom sayılar her iki taraftan da okunduğunda/yazıldığında yine kendisine eşit olan sayılardır. 2 basamaklı sayının çarpımı olan en büyük palindromik sayı 99 x 91 = 9009'dur.

3 basamaklı iki sayının çarpımı olarak ifade edilen en büyük palindromik sayı nedir?


Yaklaşım

İki sayı (i,j) olmak üzere arayacağımız palindromik sayı (i*j) olacak.

99<i<1000
99<j<1000

Aralığında bu aramayı yapacağız. Buradan da tahmin edebiliyoruz ki, işleme en düşük değerden başlamak bizim için ekstra zaman kaybı olacak. Çünkü en büyük sayı isteniyor, bu da muhtemelen aralıktaki en büyük değerlerin çarpımı arasında.

Programa hepsini belirleyip en büyüğünü bulmak yerine, yukarıda bahsettiğim aralık azaltma işlemini yapıp ne sonuç verecek diye baktım. Gereksiz işlem yapmaması için de sayı bulunduğunda döngüyü bitirdim. Bu bize yanlış sonuç verebilir, fakat hızından dolayı denemeye değer. Eğer sonuç çıkmasaydı diğer yaklaşımları deneyecektim.


Kodlama

Bir sayının palindromik olması için bu soruda belirtilmemiş ama temel şartın çift basamaklı olduğunu düşündüm, olmasa da sorun değil fakat bu soru için çift basamaklı olduğundan üstüne gitmeyeceğim.

420024 gibi bir sayı için bu işlemi ele alalım. Basamakları tek tek bir diziye aktarıyoruz ve karşılaştırıyoruz.

Basamaklara ayırma 
// temp=sayi;   ve digits[] basamakları tutan dizi
                for (int i = 0; i < digitLength; i++)
                {
                    digits[i] = temp % 10;
                    temp = temp / 10;
                }

Karşılaştırma 

dizi[0] = dizi[son]
dizi[1] = dizi[son-1]
dizi[2] = dizi[son-2]

Elemanları olacak şekilde bir karşılaştırma yapacağız.
//isP ---> sayının palindromik olup olmadığı
                for (int j = 0; j < digitLength / 2; j++)
                {
                    if (digits[j] == digits[digitLength - j - 1])
                    {
                        isP = true;
                    }
                    else
                    {
                        isP = false;
                        break;
                    }

                }

isPalindrome Fonksiyonunun Tamamı
private static bool isPalindrome(int num)
        {
            bool isP = false;
            int temp = num; int digitLength = temp.ToString().Length;
            int[] digits = new int[digitLength];


            if (digitLength % 2 == 0) // Çift sayıda basamağa sahip ise
            {
                //Sayıyı basamaklarına ayırıp bir diziye aktarıyoruz.
                for (int i = 0; i < digitLength; i++)
                {
                    digits[i] = temp % 10;
                    temp = temp / 10;
                }

                for (int j = 0; j < digitLength / 2; j++)
                {
                    if (digits[j] == digits[digitLength - j - 1])
                    {
                        isP = true;
                    }
                    else
                    {
                        isP = false;
                        break;
                    }
                }
            }

            if (isP)
                return true;

            return false;

        }

Sonuç
int i = 0, j = 0;

            for (i = 999; i >= 900; i--)
            {
                for (j = 999; j >= 900; j--)
                {
                    if (isPalindrome(i * j))
                    {
                        Console.WriteLine("{0} x {1} = {2}", i, j, i * j);
                        break;
                    }
                }
                if (isPalindrome(i * j)) break;

            }

Cevap : 993 x 913 = 906609
Çözüm 1ms'den daha kısa sürdü.