NINJA’S SHIKANJI

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
SAP LabsCultfit

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5
5 10 5 20 5
4
5 20 5 10

Sample Output 1:

True
False

Explanation For Sample Input 1:

Test Case 1:
For the first test case given ‘BILL_ARR’ is { 5, 10, 5, 20, 5 } so we print ‘True’ as we take ‘5$’ from the first customer then ‘2nd’ customer gives us ‘10$’ we give him back ‘5$’ then ‘3rd’ customer give use ‘5$’ then ‘4th’ customer give us ‘20$’ now we give him back one ‘5$’ note and one ‘10$’ note.

Test Case 2:
For the second test case given ‘BILL_ARR’ is { 5, 20, 5, 10 } so we print ‘False’ as from the first customer we take ‘5$’ note than ‘2nd’ customer give us ‘20$’ note and we don’t have required change.

Sample Input 2 :

2
3
5 10 20
7
5 5 10 5 5 20 10

Sample Output 2 :

False
True

Explanation For Sample Input 2:

Test Case 1:
For the first test case given ‘BILL_ARR’ is { 5, 10, 20} so we print ‘False’ as we take ‘5$’ from the first customer then ‘2nd’ customer gives us ‘10$’ we give him back ‘5$’ then ‘3rd’ customer give use ‘20$’ but we will not be able to give him change back.

Test Case 2:
For the second test case given ‘BILL_ARR’ is { 5, 5, 10, 5, 5, 20, 10 } so we print ‘True’ as every transaction is possible.
Hint

Can you think of storing the count of notes?

Approaches (1)
Brute 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:

  1. Firstly we declare two variables ‘FIVE’ and ‘TEN’ for storing note value and their count.
  2. 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’.
  3. If we come out of the loop we return ‘True’ in the end.
Time Complexity

O(N ), where ‘N’ is the size of the array.

 

As we are iterating through our array using a simple loop.

Space Complexity

O(1), we are using constant space.

Code Solution
(100% EXP penalty)
NINJA’S SHIKANJI
Full screen
Console