وګورئ چې ایا ایکس کولی شي په قطار کې هر سړي ته بدلون ورکړي


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon
په ليکه کې

ستونزه بیان

ایکس د آیس کریم پلورونکی دی او هلته داسې خلک شتون لري چې په a کې انتظار کوي په ليکه کې د آيسکريم اخيستل آرر [i] په قطار کې د ډیم اشنا معنی ورکوي ، د فرق احتمالي ارزښتونه 5 ، 10 او 20 دي. که د X لومړنی توازن 0 وي او د آیس کریم قیمت 5 وي نو بیا مشخص کړئ چې ایا ایکس ایا دا به وکولی شي چې په قطار کې ولاړ ټولو خلکو ته بدلون ورکړي؟ پدې توګه ستونزه دا ده "وګورئ چې ایا ایکس کولی شي په قطار کې هر سړي ته بدلون ورکړي".

وګورئ چې ایا ایکس کولی شي په قطار کې هر سړي ته بدلون ورکړي

مثالونه

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

الګوریتم چیک کول چې ایا ایکس کولی شي په قطار کې هر سړي ته بدلون ورکړي

Idea

مفکوره دا ده چې د 5 ، 10 او 20 ډومینونو تعقیب وساتي چې ایکس لري. راځئ چې دا د شمیره 5 ، د 10 شمیره او د شمېرنې 20 لخوا وښایاست. د تل لپاره د امکان تر حده د لوړ ارزښت اسعارو سره بدلون بیرته راستنیدو لپاره غوره وي. دلته ټولې درې قضیې شتون لري ،

  • تیر [i] = 5 ،
    د زیاتوالي شمیره 5
  • تیر [i] = 10 ،
    که شمیره 5> 0 ، د 10 لخوا د حساب شمیره 1 او د 5 لخوا کمی شمیره
  • تیر [i] = 20 ،
    که شمیره 10> 0 او شمیره 5> 0 ، د شمیره 20 د 1 لخوا ، د شمیرو کمول 10 او د 5 لخوا حساب 1.
    نور که حساب 5> 2 ، د 20 لخوا د حساب شمیره 1 ، د 5 لخوا د شمیرو کمول

او کړنلاره

  1. 5 د متغیر شمیره 10 ، شمېرنې 20 او شمیره 0 د XNUMX په توګه پیل کړئ.
  2. ورکړل شوي وخت تېر کړئ سور.
  3. که آر آر [i] 5 دی ، د 5 لخوا د حساب شمیره 1.
  4. که چیرې آر آر [i] 10 وي ، نو د 5 شمیره چیک کړئ> 0 ، که هو ، د 10 لخوا د حساب شمیره 1 او د 5 لخوا کمی شمیره 1 ، نو ایکس نشي کولی ټولو پیرودونکو ته بدلون ورکړي ، غلط راستنیدل.
  5. بل که آرر [i] 20 وي ، که چیرې 10 له 0 څخه لوی وي او شمیره 5 له 0 څخه لوی وي. که هو ، د شمیره 20 د 1 لخوا کم او د شمېرنې شمیره 5 او که یوځل شمیره 10 ، که نه ، نو چیک کړئ چې شمیره 5 له 2 څخه لوی ده ، که هو ، د 20 لخوا د حساب شمیره 1 او د 5 لخوا کمول 3 ، نور نو ایکس نشي کولی ټولو پیرودونکو ته بدلون ورکړي ، غلط راستنیدل.
  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

د C ++ کوډ چیک کولو لپاره که ایکس کولی شي په قطار کې هر سړي ته بدلون ورکړي

#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

د پیچلتیا تحلیل

د وخت پیچلتیا 

O (n) ، ځکه چې موږ د ن عنصر لرونکي ان پټ صف کې تېر شو. او دې الګوریتم په خطي وخت کې پرمخ وګرځاو.

د ځای پیچلتیا

O (1) ، ځکه چې مونږ هیڅ صف نه دی کارولی. موږ ډونلي 3 متغیرونه کاروو چې ثابت ځای نیسي. او پدې توګه د ځای پیچلتیا.
چیرې چې n د پیرودونکو ټوله شمیره ده.