چيڪ ڪريو ته ڇا X قطار ۾ ايندڙ هر فرد کي تبديلي آڻي سگهي ٿو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon
پنگتي حيثيت رکي ٿو

مسئلي جو بيان

ايڪس هڪ آئس ڪريم وڪڻندڙ آهي ۽ اتي جا ماڻهو ن آهن پنگتي حيثيت رکي ٿو هڪ آئس ڪريم خريد ڪرڻ. ارر [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 جي نالي جو نانءُ ٽريڪ رکو. انھن کي ڳڻپيو وڃي 5 سيٽ 10 ، شمار 20 ۽ شمار XNUMX سان اهو هميشه لاءِ بهتر آهي ته تبديلي کي واپس موٽايو وڃي جيترو ممڪن طور تي وڌيڪ قدر واري ڪرنسي سان. ڪُل ٽي ڪيس آهن ،

  • arr [i] = 5 ،
    وڌندڙ ڳڻپ 5 طرفان 1
  • arr [i] = 10 ،
    جيڪڏهن ڳڻپ 5> 0 ، واڌاري جي حساب 10 پاران 1 ۽ گهٽتائي واري شمار 5 ذريعي 1
  • arr [i] = 20 ،
    جيڪڏهن شمار 10> 0 ۽ ڳڻپ 5> 0 ، واڌو شمار 20 پاران 1 ، گھٽتائي 10 ۽ ڪٽ 5 کي 1 کان.
    ٻي صورت ۾ جيڪڏهن ڳڻپ 5> 2 ، واڌاري جي حساب 20 کان 1 ، گهٽتائي واري شمار 5 پاران 3

چرچو

  1. شروعاتي ٽي ٽي ڪيبل ڪيٽين 5 ، شمار 10 ۽ ڪٽ 20 طور 0 ڪريو.
  2. ڏنل دڳ تان صف.
  3. جيڪڏهن arr [i] 5 آهي ، واڌاري واري حساب 5 کان 1.
  4. ٻي صورت ۾ جيڪڏهن arr [i] 10 آهي ، چڪاس ڪريو جيڪڏهن ڳڻپ 5> 0 ، جيڪڏهن ها ، واڌاري واري انگ 10 پاران 1 ۽ گهٽتائي جو شمار 5 پاران 1 ، ٻي صورت ۾ ايڪس سڀني گراهڪن کي تبديلي نه ٿو ڏئي ، غلط موٽڻ.
  5. ٻي صورت ۾ جيڪڏهن arr [i] 20 آهي ، چڪاس ڪريو ته ڳڻپ 10 جو نمبر 0 کان وڏو آهي ۽ شمار 5 0 کان وڌيڪ آهي. جيڪڏهن ها ، وڌندڙ شمار 20 پاران 1 ۽ گهٽتائي جي ڳڻپ ها ، وڌندڙ شمار 5 پاران 10 ۽ گهٽتائي واري شمار 5 پاران 2 ، ٻي صورت ۾ ايڪس سڀني گراهڪن کي تبديلي نه ٿو ڏئي ، غلط موٽڻ.
  6. جيڪڏهن ايڪس سڀني گراهڪن کي تبديل ڪرڻ جي قابل هئا ، سچا موٽڻ.

ڪوڊ

جاوا ڪوڊ اهو چيڪ ڪرڻ لاءِ ته ڇا 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

سي ++ ڪوڊ چيڪ ڪرڻ لاءِ ته ڇا 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

پيچيدگي تجزيي

وقت جي پيچيدگي 

اي (ن) ، ڇاڪاڻ ته اسان عناصر کي ن عناصر هجڻ سان گڏ ڪيو آهي. ۽ اهو ٺاهيل الگورٿم کي قطار واري وقت ۾ هلائيندي.

خلائي پيچيدگي

اي (1) ، ڇاڪاڻ ته اسان ڪوبه ترتيب استعمال نه ڪيو آهي. اسان ڊونلي 3 ڪيبل استعمال ڪيا آهن جيڪي مسلسل جڳهه والاري ٿو ۽ اھڙي طرح مسلسل خلائي پيچيدگي.
جتي گراهڪن جو ڪل تعداد آهي.