Проверить, может ли X выдать сдачу каждому человеку в очереди

Опубликовано: 6 Января, 2022

Дан массив из N целых чисел, где A i обозначает банкноту, которую имеет i-й человек. Возможные валюты: 5, 10 и 20. Все N человек стоят в очереди, ожидая, чтобы купить мороженое у X, которое стоит 5 рупий. Первоначально у X начальный баланс равен 0. Проверьте, сможет ли X сделать это. предоставить сдачу всем людям, которые ждут, чтобы купить мороженое.

Примеры:

Input:a[] = {5, 5, 5, 10, 20} 
Output: YES 
When the fourth person comes to buy an ice-cream, X has three Rs 5 
change, hence X gives him 1, and now when the fifth person 
comes to buy the ice-cream, X has two Rs 5 and one Rs 10 note, hence he 
gives him one Rs 10 and one Rs 5 note. 

Input: a[] = {5, 10, 10, 20} 
Output: NO 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход состоит в том, чтобы отслеживать количество валют в 5 и 10 рупий. Валюта в 20 рупий не будет использоваться, поскольку это самая высокая валюта, которую может дать человек, и поэтому ее нельзя отдать в качестве сдачи. Инициализируйте две переменные для подсчета 5 рупий (fiveCount) и 10 рупий (tenCount). Если у человека есть валюта в размере 10 рупий и fiveCount> 0, уменьшите FiveCount и увеличьте tenCount. Если у X нет 5 рупий, то X не может дать человеку требуемую сдачу. Если у человека есть банкнота в 5 долларов, увеличьте FiveCount на единицу. Если у человека 20 рупий, то будут три условия:

  • Если fiveCount> 0 и tencount> 0, уменьшите оба.
  • В противном случае, если fiveCount> = 3, уменьшите Fivecount на три.
  • В противном случае верните false.

Если сдачу получают все люди в очереди, выведите «YES», иначе выведите «NO».

Below is the implementation of the above idea.  

C++

// C++ program to check whether X can give change
// to every person in the Queue
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if every person will
// get the change from X
int isChangeable(int notes[], int n)
{
    // To count the 5$ and 10& notes
    int fiveCount = 0;
    int tenCount = 0;
 
    // Serve the customer in order
    for (int i = 0; i < n; i++) {
 
        // Increase the number of 5$ note by one
        if (notes[i] == 5)
            fiveCount++;
        else if (notes[i] == 10) {
 
            // decrease the number of note 5$ and
            // increase 10$ note by one
            if (fiveCount > 0) {
                fiveCount--;
                tenCount++;
            }
            else
                return 0;
        }
        else {
 
            // decrease 5$ and 10$ note by one
            if (fiveCount > 0 && tenCount > 0) {
                fiveCount--;
                tenCount--;
            }
 
            // decrease 5$ note by three
            else if (fiveCount >= 3) {
                fiveCount -= 3;
            }
            else
                return 0;
        }
    }
 
    return 1;
}
// Driver Code
int main()
{
    // queue of customers with available notes.
    int a[] = { 5, 5, 5, 10, 20 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // Calling function
    if (isChangeable(a, n))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

Java

// Java program to check
// whether X can give
// change to every person
// in the Queue
import java.io.*;
 
class GFG
{
     
// Function to check if
// every person will
// get the change from X
static int isChangeable(int notes[],
                        int n)
{
    // To count the 5$
    // and 10& notes
    int fiveCount = 0;
    int tenCount = 0;
 
    // Serve the customer
    // in order
    for (int i = 0; i < n; i++)
    {
 
        // Increase the number
        // of 5$ note by one
        if (notes[i] == 5)
            fiveCount++;
        else if (notes[i] == 10)
        {
 
            // decrease the number
            // of note 5$ and
            // increase 10$ note by one
            if (fiveCount > 0)
            {
                fiveCount--;
                tenCount++;
            }
            else
                return 0;
        }
        else
        {
 
            // decrease 5$ and
            // 10$ note by one
            if (fiveCount > 0 &&
                tenCount > 0)
            {
                fiveCount--;
                tenCount--;
            }
 
            // decrease 5$
            // note by three
            else if (fiveCount >= 3)
            {
                fiveCount -= 3;
            }
            else
                return 0;
        }
    }
 
    return 1;
}
 
// Driver Code
public static void main (String[] args)
{
     
// queue of customers
// with available notes.
int a[] = {5, 5, 5, 10, 20};
int n = a.length;
 
// Calling function
if (isChangeable(a, n) > 0)
    System.out.print("YES");
else
    System.out.print("NO");
}
}
 
// This code is contributed
// by anuj_67.

Python3

# Python program to check whether X can
# give change to every person in the Queue
 
# Function to check if every person
# will get the change from X
def isChangeable(notes, n):
     
    # To count the 5$ and 10& notes
    fiveCount = 0
    tenCount = 0
     
    # Serve the customer in order
    for i in range(n):
         
        # Increase the number of 5$ note by one
        if (notes[i] == 5):
            fiveCount += 1
        elif(notes[i] == 10):
             
            # decrease the number of note 5$
            # and increase 10$ note by one
            if (fiveCount > 0):
                fiveCount -= 1
                tenCount += 1
            else:
                return 0
        else:
             
            # decrease 5$ and 10$ note by one
            if (fiveCount > 0 and tenCount > 0):
                fiveCount -= 1
                tenCount -= 1
                 
            # decrease 5$ note by three
            elif (fiveCount >= 3):
                fiveCount -= 3
            else:
                return 0
    return 1
 
# Driver Code
 
# queue of customers with available notes.
a = [5, 5, 5, 10, 20 ]
n = len(a)
 
# Calling function
if (isChangeable(a, n)):
    print("YES")
else:
    print("NO")
 
# This code is contributed by PrinciRaj1992

C#

// C# program to check
// whether X can give
// change to every person
// in the Queue
using System;
 
class GFG
{
     
// Function to check if
// every person will
// get the change from X
static int isChangeable(int []notes,
                        int n)
{
    // To count the 5$
    // and 10& notes
    int fiveCount = 0;
    int tenCount = 0;
 
    // Serve the customer
    // in order
    for (int i = 0; i < n; i++)
    {
 
        // Increase the number
        // of 5$ note by one
        if (notes[i] == 5)
            fiveCount++;
        else if (notes[i] == 10)
        {
 
            // decrease the number
            // of note 5$ and
            // increase 10$ note by one
            if (fiveCount > 0)
            {
                fiveCount--;
                tenCount++;
            }
            else
                return 0;
        }
        else
        {
 
            // decrease 5$ and
            // 10$ note by one
            if (fiveCount > 0 &&
                tenCount > 0)
            {
                fiveCount--;
                tenCount--;
            }
 
            // decrease 5$
            // note by three
            else if (fiveCount >= 3)
            {
                fiveCount -= 3;
            }
            else
                return 0;
        }
    }
 
    return 1;
}
 
// Driver Code
public static void Main ()
{
     
// queue of customers
// with available notes.
int []a = {5, 5, 5, 10, 20};
int n = a.Length;
 
// Calling function
if (isChangeable(a, n) > 0)
    Console.WriteLine("YES");
else
    Console.WriteLine("NO");
}
}
 
// This code is contributed
// by anuj_67.

Javascript

<script>
    // Javascript program to check
    // whether X can give
    // change to every person
    // in the Queue
     
    // Function to check if
    // every person will
    // get the change from X
    function isChangeable(notes, n)
    {
        // To count the 5$
        // and 10& notes
        let fiveCount = 0;
        let tenCount = 0;
 
        // Serve the customer
        // in order
        for (let i = 0; i < n; i++)
        {
 
            // Increase the number
            // of 5$ note by one
            if (notes[i] == 5)
                fiveCount++;
            else if (notes[i] == 10)
            {
 
                // decrease the number
                // of note 5$ and
                // increase 10$ note by one
                if (fiveCount > 0)
                {
                    fiveCount--;
                    tenCount++;
                }
                else
                    return 0;
            }
            else
            {
 
                // decrease 5$ and
                // 10$ note by one
                if (fiveCount > 0 &&
                    tenCount > 0)
                {
                    fiveCount--;
                    tenCount--;
                }
 
                // decrease 5$
                // note by three
                else if (fiveCount >= 3)
                {
                    fiveCount -= 3;
                }
                else
                    return 0;
            }
        }
 
        return 1;
    }
     
    // queue of customers
    // with available notes.
    let a = [5, 5, 5, 10, 20];
    let n = a.length;
 
    // Calling function
    if (isChangeable(a, n) > 0)
        document.write("YES");
    else
        document.write("NO");
     
</script>
Output: 
YES