تحقق مما إذا كان بإمكان X إحداث تغيير لكل شخص في قائمة الانتظار


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون
طابور

المشكلة بيان

X هو بائع آيس كريم وهناك عدد من الأشخاص ينتظرون في طابور لشراء الآيس كريم. تشير Arr [i] إلى التسمية التي يمتلكها الشخص الموجود في قائمة الانتظار ، والقيم المحتملة للفئات هي 5 و 10 و 20. إذا كان الرصيد الأولي لـ X يساوي 0 وتكلفة الآيس كريم هي 5. ثم حدد ما إذا كان X أم لا سوف تكون قادرة على إحداث تغيير لجميع الأشخاص الذين يقفون في قائمة الانتظار؟ وبالتالي فإن المشكلة هي "تحقق مما إذا كان بإمكان X إحداث تغيير لكل شخص في قائمة الانتظار".

تحقق مما إذا كان بإمكان X إحداث تغيير لكل شخص في قائمة الانتظار

أمثلة

arr[] = {5, 5, 10, 20}
true
arr[] = {10, 5, 5, 5, 5, 5}
false
arr[] = {5, 5, 5, 20, 5, 10}
true

خوارزمية للتحقق مما إذا كان بإمكان X إحداث تغيير لكل شخص في قائمة الانتظار

فكرة

الفكرة هي تتبع الفئات 5 و 10 و 20 التي يمتلكها X. دع هذه تمثل بواسطة count5 و count10 و count20. من الأفضل دائمًا إرجاع التغيير بأكبر عملة ذات قيمة عالية قدر الإمكان. هناك إجمالي ثلاث حالات ،

  • arr [i] = 5 ،
    زيادة العد 5 في 1
  • arr [i] = 10 ،
    إذا كان العد 5> 0 ، قم بزيادة العدد 10 بمقدار 1 وإنقاص العدد 5 بمقدار 1
  • arr [i] = 20 ،
    إذا كان count10> 0 و count5> 0 ، قم بزيادة العد 20 × 1 ، وانقاص العدد 10 ، وعد 5 × 1.
    عدا ذلك ، إذا كان العد 5> 2 ، فإن زيادة العد 20 × 1 ، والتناقص العد 5 في 3

الرسالة

  1. قم بتهيئة ثلاثة متغيرات العد 5 و count10 و count20 كصفر.
  2. اجتياز المعطى مجموعة.
  3. إذا كانت قيمة arr [i] 5 ، تتم زيادة العد 5 × 1.
  4. وإلا إذا كانت قيمة arr [i] 10 ، فتحقق مما إذا كان count5> 0 ، وإذا كانت الإجابة بنعم ، قم بزيادة العد 10 x 1 و decrement count5 x 1 ، وإلا فلن تتمكن X من تقديم تغيير لجميع العملاء ، فقم بإرجاع القيمة false.
  5. وإلا إذا كانت قيمة arr [i] 20 ، فتحقق مما إذا كان العدد 10 أكبر من 0 وكان count5 أكبر من 0. إذا كانت الإجابة بنعم ، قم بزيادة العدد 20 × 1 وعدد التناقص 5 والعدد 10 بواحد ، إذا لم يكن كذلك ، تحقق مما إذا كان العدد 5 أكبر من 2 نعم ، زيادة العد 20 في 1 والتناقص عدد 5 في 3 ، وإلا X لا يمكن أن تعطي التغيير لجميع العملاء ، وإرجاع كاذبة.
  6. إذا كان X قادرًا على إعادة التغيير إلى جميع العملاء ، فقم بإرجاعه صحيحًا.

رمز

كود Java للتحقق مما إذا كان X يمكنه إحداث تغيير لكل شخص في قائمة الانتظار

class CheckIfXCanGiveChangeToEveryPersonStandingInQueue {
    private static boolean checkIfPossible(int[] arr) {
        // initialize count0, counnt10 and count20 as 0
        int count5 = 0, count10 = 0, count20 = 0;
        
        // traverse in the array
        for (int i = 0; i < arr.length; i++) {
            // Case 1 : arr[i] = 5
            if (arr[i] == 5) {
                // increment count5 by 1
                count5++;
            }
            // Case 2 : arr[i] = 10
            else if (arr[i] == 10) {
                // if there are some 5 rs coins return 1
                if (count5 > 0) {
                    // decrement count5 by 1 and increment count10 by 1
                    count5--;
                    count10++;
                } else {
                    // if there are not, X cannot give change to everyone
                    return false;
                }
            }
            // Case 3 : arr[i] = 20
            else {
                // if there are some 10 rs coins and some 5 rs coin return one one each
                if (count10 > 0 && count5 > 0) {
                    count10--;
                    count5--;
                    count20++;
                } else if (count5 > 2) {
                    // else if there are 3 or more 5 rs coins return 3
                    count5 -= 3;
                    count20++;
                } else {
                    // X cannot give chnage to everyone
                    return false;
                }
            }
        }

        // X can give change to everyone
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 5, 10, 20};
        System.out.println(checkIfPossible(arr1));

        // Example 2
        int arr2[] = new int[] {10, 5, 5, 5, 5, 5};
        System.out.println(checkIfPossible(arr2));

        // Example 3
        int arr3[] = new int[]{5, 5, 5, 20, 5, 10};
        System.out.println(checkIfPossible(arr3));
    }
}
true
false
true

كود C ++ للتحقق مما إذا كان بإمكان X إحداث تغيير لكل شخص في قائمة الانتظار

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

bool checkIfPossible(int *arr, int n) {
    // initialize count0, count10 and count20 as 0
    int count5 = 0, count10 = 0, count20 = 0;

    // traverse in the array
    for (int i = 0; i < n; i++) {
        // Case 1 : arr[i] = 5
        if (arr[i] == 5) {
            // increment count5 by 1
            count5++;
        }
        // Case 2 : arr[i] = 10
        else if (arr[i] == 10) {
            // if there are some 5 rs coins return 1
            if (count5 > 0) {
                // decrement count5 by 1 and increment count10 by 1
                count5--;
                count10++;
            } else {
                // if there are not, X cannot give change to everyone
                return false;
            }
        }
        // Case 3 : arr[i] = 20
        else {
            // if there are some 10 rs coins and some 5 rs coin return one one each
            if (count10 > 0 && count5 > 0) {
                count10--;
                count5--;
                count20++;
            } else if (count5 > 2) {
                // else if there are 3 or more 5 rs coins return 3
                count5 -= 3;
                count20++;
            } else {
                // X cannot give chnage to everyone
                return false;
            }
        }
    }

    // X can give change to everyone
    return true;
}

int main() {
    // Example 1
    int arr1[] = {5, 5, 10, 20};
    if (checkIfPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {10, 5, 5, 5, 5, 5};
    if (checkIfPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    int arr3[] = {5, 5, 5, 20, 5, 10};
    if (checkIfPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
}
true
false
true

تحليل التعقيد

تعقيد الوقت 

على)، لأننا اجتزنا خلال مصفوفة الإدخال التي تحتوي على n من العناصر. وهذا جعل الخوارزمية تعمل في الوقت الخطي.

تعقيد الفضاء

يا (1) ، لأننا لم نستخدم أي مجموعة. لقد استخدمنا 3 متغيرات تأخذ مساحة ثابتة. وبالتالي ثابت التعقيد المكاني.
حيث n هو العدد الإجمالي للعملاء.