PROBLEM LINKS :
Stacks , Queue , Modulo , Modular Arithmetic , Modular Multiplication
Given N chefs in a queue , each chef may delegate his/her task to the junior least ahead of him and go away . The Head Chefs fearfulness of the scenario is the difference in index of the two positions + 1 . Head Chef’s total fearfulness is product of individual fearfulness corresponding to each chef . Find total fearfulness . In case no junior lies ahead the fearfulness is 1 .
The Naive Solution :
For each chef look at all chefs ahead of this chef in the queue till you find a junior chef and then update the Head Chef’s fearfulness . This has a time complexity of O(N^2) .
Using Stacks :
Start with given queue and an empty stack(of a structure of numbers and their indexes) .
For each chef put him on a stack if the top of stack is not senior to him otherwise pop out as many senior chefs from the stack as possible ( updating Head Chef’s fearfulness at each pop ) and finally push the chef on the stack .
The time complexity of this solution is O(N) .
Example Using Stacks :
Given the queue , 8 3 7 8 9 12 13 11 3 4
Initialize ans = 1 ; sp = 1000000007
Step One : Stack == [8,1]
Step Two : Stack == [3,2] ( ans *= ( 2 - 1 + 1 ) , ans %= sp => ans = 2 )
Step Three : Stack == [3,2] [7,3] ( ans remains same )
Step Four : Stack == [3,2] [7,3] [8,4] ( ans remains same )
Step Five : Stack == [3,2] [7,3] [8,4] [9,5] ( ans remains same )
Step Six : Stack == [3,2] [7,3] [8,4] [9,5] [12,6] ( ans remains same )
Step Seven : Stack == [3,2] [7,3] [8,4] [9,5] [12,6] [13,7] ( ans remains same )
Step Seven : Stack = [3,2] [7,3] [8,4] [9,5] [11,8] ( Two elements are popped out , ans need to be multiplied by 2 and 3 corresponding to each of pop . So ans = 12 )
Step Eight : Stack == [3,2] [3,9] ( Four elements are popped out . ans need to be multiplied (modularly) by 2 , 5 , 6 , 7 )
Step Nine : Stack == [3,2] [3,9] [4,10] .
Finish and output ans .
Point to Remember :
Take modulus with the special number given after each multiplication .