Last Updated: 9 Apr, 2021

NINJA’S SHIKANJI

Easy

Asked in companies

Solve now

Problem statement

Ninja opened a shikanji’s stall to earn a living for him. In his stall, each shikanji drinks cost ‘5$’. Customers are standing in the form queue and each customer either pays ‘5$, 10$, 20$ ‘ so now Ninja has to give them change so that each customer exactly pays ‘5$’.

So now help the ninja to find out whether he is able to charge exactly ‘5$’ from each customer by providing them the change.

So your task is to write a code to check whether ninja can provide change to the customer if they paid extra to him. You will be provided with the ‘BILL_ARR’ array denoting the amount paid by each customer you have to return ‘True’ if it is possible else you have to return ‘False’.

Example:

Suppose given ‘BILL_ARR’ array is { 5, 5, 5, 10, 20 } so we return ‘True’ for this test case as from first ‘3’ customers we take ‘5$’ from each customer then ‘4th’ customer give ‘10$’ we give him ‘5$’ back now we have ‘2’, ‘5$’ note and ‘1’, ‘10$’ note than ‘5th’ customer give ‘20$’ so we give him back one ‘10$’ and one ‘5$’ note.

Input Format:

The first line of input contains a ‘T’ number of test cases.

The first line of each test case contains an integer ‘N’ i.e size of the array ‘BILL_ARR’.

The second line of each test case contains an array ‘BILL_ARR’, where ‘BILL_ARR[i]’  denotes the money paid for ‘i-th’ shikanji.

Output Format:

For each test case, print ‘True’ if it is possible else print ‘False’.

Note:

1. You don’t have any changes at starting.
2. You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
BILL_ARR[i]  = [ ‘5’, ‘10’, ‘20’ ]  

Where ‘T’ represents the number of test cases and ‘N’ represents the size of the array and ‘BILL_ARR[i]’ represents the elements of the array.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: The idea here is to use a ‘2’ variables for count instead of a map and whenever we strike some note can check the count of variables to check whether we can able to give change or not.

The algorithm is as follows:

Firstly we declare two variables ‘FIVE’ and ‘TEN’ for storing note value and their count.
We start iterating our ‘BILL_ARR’ and if we strike :
- Note with the value ‘5$’ we simply increase the count of ‘5$’ in the variable ‘FIVE’.
- Note with value ‘10$’ we check if the count of variable ‘FIVE’ is greater than ‘0’
  - If it exists we increase the count of note value ‘10$’ by 1 and decrease the value of note value ‘5$’ by ‘1’.
  - Else we return ‘False’.
- Note with value ‘20$’ we check if the count of variable ‘TEN’ is greater than ‘0’ and count of variable ‘FIVE’ is greater than ‘0’ or count of five is greater than ‘2’
  - If it exists:
    - We check whether we give him 3, ‘5$’ notes or 1, ‘5$’ note and 1, ‘10$’ note according to that we decrease the count.
  - Else we return ‘False’.
If we come out of the loop we return ‘True’ in the end.

Solve now