ക്യൂവിലെ ഓരോ വ്യക്തിക്കും മാറ്റം നൽകാൻ എക്‌സിന് കഴിയുമോയെന്ന് പരിശോധിക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ
വരി

പ്രശ്നം പ്രസ്താവന

എക്സ് ഒരു ഐസ്ക്രീം വിൽപ്പനക്കാരനാണ്, കൂടാതെ ഒരു ആളുകൾ കാത്തിരിക്കുന്നു വരി ഒരു ഐസ്ക്രീം വാങ്ങാൻ. Arr [i] ക്യൂവിലുള്ള ith വ്യക്തിയെ സൂചിപ്പിക്കുന്നു, വിഭാഗങ്ങളുടെ സാധ്യമായ മൂല്യങ്ങൾ 5, 10, 20 എന്നിവയാണ്. X ന്റെ പ്രാരംഭ ബാലൻസ് 0 ഉം ഒരു ഐസ്ക്രീമിന്റെ വില 5 ഉം ആണെങ്കിൽ 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 വിഭാഗങ്ങളുടെ ട്രാക്ക് സൂക്ഷിക്കുക എന്നതാണ് ആശയം. ഇവയെ count5, count10, count20 എന്നിവ പ്രതിനിധീകരിക്കട്ടെ. കഴിയുന്നത്ര ഉയർന്ന മൂല്യമുള്ള കറൻസി ഉപയോഗിച്ച് മാറ്റം നൽകുന്നത് എല്ലായ്പ്പോഴും അനുയോജ്യമാണ്. ആകെ മൂന്ന് കേസുകളുണ്ട്,

  • arr [i] = 5,
    വർദ്ധനവ് എണ്ണം 5 കൊണ്ട് 1
  • arr [i] = 10,
    ക 5 ണ്ട് 0> 10 ആണെങ്കിൽ, ക count ണ്ട് 1 നെ 5 ഉം ഇൻ‌ക്രിമെൻറ് ക 1 ണ്ട് XNUMX ഉം വർദ്ധിപ്പിക്കുക
  • arr [i] = 20,
    ക 10 ണ്ട് 0> 5 ഉം ക 0 ണ്ട് 20> 1 ഉം ആണെങ്കിൽ, ക count ണ്ട് 10 നെ 5, ഇൻ‌ക്രിമെൻറ് ക count ണ്ട് 1, ക XNUMX ണ്ട് XNUMX XNUMX
    ക count ണ്ട് 5> 2 ആണെങ്കിൽ, ക count ണ്ട് 20 എണ്ണം 1, ഇൻ‌ക്രിമെൻറ് ക 5 ണ്ട് 3 XNUMX

സമീപനം

  1. Count5, count10, count20 എന്നിങ്ങനെ മൂന്ന് വേരിയബിളുകൾ 0 ആയി ആരംഭിക്കുക.
  2. തന്നിരിക്കുന്നവയിലൂടെ സഞ്ചരിക്കുക ശ്രേണി.
  3. Ar [i] 5 ആണെങ്കിൽ, എണ്ണം 5 വർദ്ധിപ്പിക്കുക.
  4. Arr [i] 10 ആണെങ്കിൽ, count5> 0 ആണോയെന്ന് പരിശോധിക്കുക, അതെ എങ്കിൽ, count10 ന്റെ വർദ്ധനവ് 1 ഉം count5 ന്റെ എണ്ണം 1 ഉം കുറയ്ക്കുക, അല്ലെങ്കിൽ X ന് എല്ലാ ഉപഭോക്താക്കളിലും മാറ്റം നൽകാൻ കഴിയില്ല, തെറ്റായി മടങ്ങുക.
  5. Arr [i] 20 ആണെങ്കിൽ, count10 0 നെക്കാൾ വലുതും count5 0 നെക്കാൾ വലുതാണോയെന്ന് പരിശോധിക്കുക. അതെ, ക count ണ്ട് 20 നെ 1 ഉം ഇൻ‌ക്രിമെൻറ് ക count ണ്ട് 5 ഉം 10 ഉം വർദ്ധിപ്പിക്കുക, അല്ലാത്തപക്ഷം എക്സ് എല്ലാ ഉപഭോക്താക്കളിലും മാറ്റം വരുത്താൻ‌ കഴിയില്ല, തെറ്റായി മടങ്ങുക.
  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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത 

O (n), കാരണം n ഘടകങ്ങളുള്ള ഇൻപുട്ട് അറേയിലൂടെ ഞങ്ങൾ സഞ്ചരിച്ചു. ഇത് അൽ‌ഗോരിതം രേഖീയ സമയത്ത് പ്രവർത്തിപ്പിക്കാൻ സഹായിച്ചു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം ഞങ്ങൾ ഒരു ശ്രേണിയും ഉപയോഗിച്ചിട്ടില്ല. സ്ഥിരമായ ഇടം എടുക്കുന്ന ഡോൺലി 3 വേരിയബിളുകൾ ഞങ്ങൾ ഉപയോഗിച്ചു. അങ്ങനെ സ്ഥിരമായ സ്ഥല സങ്കീർണ്ണത.
ഇവിടെ n എന്നത് മൊത്തം ഉപഭോക്താക്കളുടെ എണ്ണം.