9. Palindrome Number حل المسئلة مع الشرح

يمكنك زيارة المسئلة في الموقع الرسمي leetcode من هنا

نص السؤال

إذا كانت المعطيات رقم x أوجد إذا كان x يصح أن يكون palindrome أم لا (الرقم يكون palindrome إذا كان يُقرأ من اليمين إلى اليسار كما يُقرأ من اليسار إلى اليمين)

مثال 1

• المعطيات : x = 121
• النتيجة : true

مثال 2

• المعطيات: x = -121 .
• النتيجة : false

مثال 3

• المعطيات: x = 10 .
• النتيجة : false .

شرح الحل

طبعاً هنا قد يخطر على بال أحدنا أنه يمكن تحويل الرقم إلى string ثم نقوم بسهولة بعمل مؤشرين (two pointers) للتحقق من أن الرقم palindrome أم لا ولكن هذا الحل يستخدم مساحة لتحويل الرقم إلى string وهناك حل يتم بدون استخدام مساحة إضافية وهو كالتالي:

هنا نلاحظ أن الأرقام السالبة لا يمكن أن تكون palindrome بسبب العلامة (-) .

وأيضاً الأرقام التي على يمينها صفر كالرقم 10 أو 120 مثلاً ، أيضاً لا يمكن أن يكونو palindrome وذلك لأن من المستحيل وجود رقم على يساره صفر وبما أن الرقم على يمينه صفر فأنه لا يمكن أن يكون الرقم palindrome إذا في أول الحل نتحقق أن الرقم ليس بسالب ولا على يمينه صفر ونحقق ذلك كالتالي:

الرقم سالب إذا كان أقل من صفر .

الرقم على يمينه صفر إذا كان يقبل القسمة على 10 .

وبعد ذلك يكون الحل بإختصار هو أن نقلب الرقم ثم نتحقق إذا كان الرقم مقلوباً يساوي الرقم الأصلي.

وكيف نقلب الرقم ؟

نصنع متغيرين أحدهما اسمه الرقم المؤقت لتخزين نسخه من الرقم الأصلي والثاني لتخزين الرقم المسعكوس.

let tempNum = x;
let reversedNum = 0;

نقوم بحساب الرقم الأيمن عن طريق حساب باقي قسمة الرقم على 10 والناتج هو الرقم الأول من اليمين وهو المطلوب فمثلاً الرقم 121 ناتج باقي قسمته على 10 يكون 1

ثم نقوم بقسمة الرقم 121 على 10 ليكون الناتج 12.1 ونخزن الناتج في متغير من نوع integer أو باستخدام الدوال البرمجية نتخلص من القيمة العشرية ليتبقى معنا 12 ونخزن هذه القيمة في متغير مؤقت.

ثم نقوم بنفس العملية التي قمنا بها على الرقم 121 وهي حساب باقي قسمة الرقم 12 على 10 لإيجاد الرقم الأيمن وفي هذه الحالة سيكون 2 ولكن كيف نضيف الإثنين إلى 1 فكر في الأمر قليلاً ستجد أن الإثنين لكي توضع على يمين الواحد (لاحظ أن هذه الإثنين كانت على يسار الواحد في الرقم الأصلي ونحن نريد قلب الرقم فيجب أن نضع ال 2 إلى يمين الواحد) يجب أن يكون الواحد بمثابة العشرات للإثنين أو نضع صفر بالجانب الأيمن من الواحد لكي نستطيع أن نجمع عليه 2 ليصير الرقم 12 ، وكيف نحقق ذلك ؟ عن طريق ضرب الرقم 1 في 10 ثم جمع الرقم 2 عليه.

إذاً نضرب الرقم الناتج من العملية السابقة في 10 ثم نجمع عليه ناتج باقي قسمة الرقم المؤقت على 10.

أو بمعنى آخر الرقم المعكوس كل مرة يساوي الرقم المعكوس السابق × 10 + الرقم المؤقت % 10 .

ولا ننسى عمل تحديث للرقم المؤقت بقسمته على 10 ثم حذف القيمة العشرية.

reversedNum = reversedNum * 10 + tempNum % 10;
tempNum = Math.trunc(tempNum / 10)

فبعد هذه العملية ستكون القيم الجديدة كالتالي :

إذاً يجب علينا أن نظل نقوم بهذه العملية حتى يكون ال الرقم المؤقت (tempNum) يساوي صفر.

while(tempNum > 0){
    reversedNum = reversedNum * 10 + tempNum % 10;
    tempNum = Math.trunc(tempNum / 10)
}

العملية التالية ستكون :

وهكذا حتى تنتهي ال while loop وفي النهاية نعود من البرنامج بالتحقق إذا كان الرقم المؤقت tempNum يساوي الرقم الأصلي x أم لا.

function isPalindrome(x: number): boolean {
    let tempNum = x;
    let reversedNum = 0;
    while(tempNum > 0){
        reversedNum = reversedNum * 10 + tempNum % 10;
        tempNum = Math.trunc(tempNum / 10)
    }
    return reversedNum === x;
};