ಕ್ಯೂನಲ್ಲಿರುವ ಪ್ರತಿಯೊಬ್ಬ ವ್ಯಕ್ತಿಗೂ ಎಕ್ಸ್ ಬದಲಾವಣೆಯನ್ನು ನೀಡಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್
ಕ್ಯೂ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಎಕ್ಸ್ ಐಸ್ ಕ್ರೀಮ್ ಮಾರಾಟಗಾರ ಮತ್ತು ಎ ನಲ್ಲಿ ಜನರು ಕಾಯುತ್ತಿದ್ದಾರೆ ಕ್ಯೂ ಐಸ್ ಕ್ರೀಮ್ ಖರೀದಿಸಲು. ಅರ್ [i] ಕ್ಯೂನಲ್ಲಿರುವ ಇಥ್ ವ್ಯಕ್ತಿಯು ಹೊಂದಿರುವ ಪಂಗಡವನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಪಂಗಡಗಳ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳು 5, 10 ಮತ್ತು 20 ಆಗಿದೆ. ಎಕ್ಸ್ ನ ಆರಂಭಿಕ ಸಮತೋಲನ 0 ಮತ್ತು ಐಸ್ ಕ್ರೀಂನ ಬೆಲೆ 5 ಆಗಿದ್ದರೆ ಎಕ್ಸ್ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸಿ ಸರದಿಯಲ್ಲಿ ನಿಂತಿರುವ ಎಲ್ಲ ಜನರಿಗೆ ಬದಲಾವಣೆ ನೀಡಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ? ಹೀಗಾಗಿ ಸಮಸ್ಯೆ “ಕ್ಯೂನಲ್ಲಿರುವ ಪ್ರತಿಯೊಬ್ಬ ವ್ಯಕ್ತಿಗೂ ಎಕ್ಸ್ ಬದಲಾವಣೆಯನ್ನು ನೀಡಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಿ”.

ಕ್ಯೂನಲ್ಲಿರುವ ಪ್ರತಿಯೊಬ್ಬ ವ್ಯಕ್ತಿಗೂ ಎಕ್ಸ್ ಬದಲಾವಣೆಯನ್ನು ನೀಡಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಿ

ಉದಾಹರಣೆಗಳು

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

ಕ್ಯೂನಲ್ಲಿರುವ ಪ್ರತಿಯೊಬ್ಬ ವ್ಯಕ್ತಿಗೂ ಎಕ್ಸ್ ಬದಲಾವಣೆಯನ್ನು ನೀಡಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಅಲ್ಗಾರಿದಮ್

ಐಡಿಯಾ

ಎಕ್ಸ್ ಹೊಂದಿರುವ 5, 10 ಮತ್ತು 20 ರ ಪಂಗಡಗಳ ಜಾಡು ಹಿಡಿಯುವುದು ಇದರ ಆಲೋಚನೆ. ಇವುಗಳನ್ನು ಎಣಿಕೆ 5, ಎಣಿಕೆ 10 ಮತ್ತು ಎಣಿಕೆ 20 ಪ್ರತಿನಿಧಿಸಲಿ. ಸಾಧ್ಯವಾದಷ್ಟು ಹೆಚ್ಚಿನ ಮೌಲ್ಯದ ಕರೆನ್ಸಿಯೊಂದಿಗೆ ಬದಲಾವಣೆಯನ್ನು ಹಿಂದಿರುಗಿಸುವುದು ಯಾವಾಗಲೂ ಸೂಕ್ತವಾಗಿದೆ. ಒಟ್ಟು ಮೂರು ಪ್ರಕರಣಗಳಿವೆ,

  • 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, ಇಲ್ಲದಿದ್ದರೆ X ಎಲ್ಲಾ ಗ್ರಾಹಕರಿಗೆ ಬದಲಾವಣೆಯನ್ನು ನೀಡಲು ಸಾಧ್ಯವಿಲ್ಲ, ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ.
  5. Arr [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

ಕ್ಯೂನಲ್ಲಿರುವ ಪ್ರತಿಯೊಬ್ಬ ವ್ಯಕ್ತಿಗೂ ಎಕ್ಸ್ ಬದಲಾವಣೆಯನ್ನು ನೀಡಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಸಿ ++ ಕೋಡ್

#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 ಎಂಬುದು ಒಟ್ಟು ಗ್ರಾಹಕರ ಸಂಖ್ಯೆ.