ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਕਤਾਰ ਵਿੱਚ ਹਰੇਕ ਵਿਅਕਤੀ ਨੂੰ ਤਬਦੀਲੀ ਦੇ ਸਕਦਾ ਹੈ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ
ਕਤਾਰ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਐਕਸ ਇੱਕ ਆਈਸ ਕਰੀਮ ਵੇਚਣ ਵਾਲਾ ਹੈ ਅਤੇ ਇੱਥੇ ਏ ਲੋਕ ਉਡੀਕ ਰਹੇ ਹਨ ਪੂਛ ਇਕ ਆਈਸ ਕਰੀਮ ਖਰੀਦਣ ਲਈ. ਐਰ [i] ਕਤਾਰ ਵਿਚਲੇ ਸੰਪੰਨ ith ਵਿਅਕਤੀ ਦਾ ਸੰਕੇਤ ਕਰਦਾ ਹੈ, ਸੰਪ੍ਰਦਾਵਾਂ ਦੇ ਸੰਭਾਵਤ ਮੁੱਲ 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ਂਟ XNUMX ਅਤੇ ਕਾXNUMXਂਟ XNUMX ਦੁਆਰਾ ਦਰਸਾਇਆ ਜਾਵੇ. ਵੱਧ ਤੋਂ ਵੱਧ ਮੁੱਲ ਦੀ ਮੁਦਰਾ ਨਾਲ ਤਬਦੀਲੀ ਵਾਪਸ ਕਰਨਾ ਹਮੇਸ਼ਾਂ ਅਨੁਕੂਲ ਹੁੰਦਾ ਹੈ. ਇੱਥੇ ਕੁਲ ਤਿੰਨ ਕੇਸ ਹਨ,

  • ਅਰ [i] = 5,
    5 ਦੁਆਰਾ ਵਾਧਾ ਗਿਣਤੀ
  • ਅਰ [i] = 10,
    ਜੇ ਕਾ5ਂਟ 0> 10, ਇਨਕਰੀਮੈਂਟ 1 ਦੀ ਗਿਰਾਵਟ ਅਤੇ ਗਿਰਾਵਟ ਕਾਉਂਟ 5 ਦੁਆਰਾ 1
  • ਅਰ [i] = 20,
    ਜੇ ਗਿਣਤੀ 10> 0 ਅਤੇ ਕਾ5ਂਟ 0> 20, ਇਨਕਰੀਮੈਂਟ 1, 10 ਨਾਲ, ਗਿਰਾਵਟ 5 ਅਤੇ ਗਿਰਾਵਟ 1 ਦੁਆਰਾ XNUMX.
    ਹੋਰ ਜੇ ਕਾ5ਂਟ 2> 20, ਇਨਕਰੀਮੈਂਟ 1, 5 ਨਾਲ, ਗਿਰਾਵਟ ਕਾਉਂਟ 3 ਦੁਆਰਾ XNUMX

ਪਹੁੰਚ

  1. ਤਿੰਨ ਵੇਰੀਏਬਲ ਕਾਉਂਟੀ 5, ਕਾ10ਂਟ 20 ਅਤੇ ਕਾਉਂਟ 0 ਨੂੰ XNUMX ਦੇ ਤੌਰ ਤੇ ਅਰੰਭ ਕਰੋ
  2. ਦਿੱਤੇ ਗਏ ਨੂੰ ਪਾਰ ਕਰੋ ਐਰੇ.
  3. ਜੇ ਅਰਿ [i] 5 ਹੈ, ਇੰਕਰੀਮੈਂਟ ਕਾਉਂਟ 5 ਦੁਆਰਾ.
  4. ਨਹੀਂ ਤਾਂ ਜੇਕਰ ਏਰਰ [i] 10 ਹੈ, ਜਾਂਚ ਕਰੋ ਤਾਂ ਕਾ5ਂਟ 0> 10, ਜੇ ਹਾਂ, ਇਨਕਰੀਮੈਂਟ ਕਾਉਂਟ 1 ਦੁਆਰਾ 5 ਅਤੇ ਘੱਟ ਗਿਰਾਵਟ 1 ਦੁਆਰਾ XNUMX, ਨਹੀਂ ਤਾਂ ਐਕਸ ਸਾਰੇ ਗਾਹਕਾਂ ਨੂੰ ਬਦਲਾਅ ਨਹੀਂ ਦੇ ਸਕਦਾ, ਗਲਤ ਵਾਪਸ ਆਓ.
  5. ਹੋਰ ਜੇ ਅਰੇ [i] 20 ਹੈ, ਜਾਂਚ ਲਓ ਕਿ ਗਿਣਤੀ 10 0 ਤੋਂ ਵੱਡਾ ਹੈ ਅਤੇ ਕਾਉਂਟੀ 5 0 ਤੋਂ ਵੱਡਾ ਹੈ। ਜੇ ਹਾਂ, ਤਾਂ ਵਾਧਾ 20, 1 ਨਾਲ ਅਤੇ ਗਿਰਾਵਟ ਕਾਉਂਟ 5 ਅਤੇ ਕਾਉਂਟ 10 ਇਕ ਨਾਲ, ਜੇ ਨਹੀਂ, ਤਾਂ ਜਾਂਚ ਕਰੋ ਕਿ ਕਾ5ਂਟ 2 20 ਤੋਂ ਵੱਡਾ ਹੈ, ਜਾਂ ਹਾਂ, ਇਨਕਰੀਮੈਂਟ 1 ਨੂੰ 5 ਨਾਲ ਅਤੇ ਗਿਰਾਵਟ ਕਾਉਂਟ 3 ਦੁਆਰਾ XNUMX, ਨਹੀਂ ਤਾਂ X ਸਾਰੇ ਗਾਹਕਾਂ ਨੂੰ ਬਦਲਾਅ ਨਹੀਂ ਦੇ ਸਕਦਾ, ਗਲਤ ਵਾਪਸ ਆਵੇਗਾ.
  6. ਜੇ ਐਕਸ ਸਾਰੇ ਗਾਹਕਾਂ ਨੂੰ ਤਬਦੀਲੀ ਵਾਪਸ ਕਰਨ ਦੇ ਯੋਗ ਸੀ, ਤਾਂ ਸਹੀ ਵਾਪਸ ਆਓ.

ਕੋਡ

ਜਾਵਾ ਕੋਡ ਦੀ ਜਾਂਚ ਕਰਨ ਲਈ ਕਿ ਕੀ ਕਤਾਰ ਵਿੱਚ ਹਰੇਕ ਵਿਅਕਤੀ ਨੂੰ ਤਬਦੀਲੀ ਦੇ ਸਕਦੀ ਹੈ

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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ 

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਐਨ ਐਲੀਮੈਂਟਸ ਵਾਲੀ ਇਨਪੁਟ ਐਰੇ ਵਿਚੋਂ ਲੰਘੇ ਹਾਂ. ਅਤੇ ਇਸ ਨੂੰ ਐਲਗੀਰਿਥਮ ਨੂੰ ਲੰਬੇ ਸਮੇਂ ਵਿੱਚ ਚਲਾਉਣ ਲਈ ਬਣਾਇਆ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1), ਕਿਉਂਕਿ ਅਸੀਂ ਕੋਈ ਐਰੇ ਨਹੀਂ ਵਰਤੀ ਹੈ. ਸਾਡੇ ਕੋਲ ਡੋਲੀ 3 ਵੇਰੀਏਬਲਸ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਗਈ ਹੈ ਜੋ ਨਿਰੰਤਰ ਜਗ੍ਹਾ ਲੈਂਦੀ ਹੈ. ਅਤੇ ਇਸ ਤਰ੍ਹਾਂ ਨਿਰੰਤਰ ਸਪੇਸ ਗੁੰਝਲਤਾ.
ਜਿੱਥੇ n ਗਾਹਕਾਂ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਹੈ.