Cakes

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in company
Google

Problem statement

You have 'N' cakes of different names. You want to choose exactly 3 cakes out of these 'N' cakes. The name of the ith cake is 'S[i]' (0 <= i < 'N'). The three chosen cakes should follow the following conditions.

The name of the cake should start with 'c', 'a', 'k', 'e', or 's'.
No two cakes should begin with the same letter.

Return the number of ways to choose three cakes irrespective of the order.

Note : Assume 0-based indexing.

For example: 
Let 'N' = 4, S = ["choco", "apple", "kesar", "strawberry"].
There exist 4 different ways to choose three cakes following all the required conditions i.e. {"choco", "apple", "kesar"}, {"choco", "apple", "strawberry"}, {"choco", "strawberry", "kesar"}, {"strawberry", "apple", "kesar"}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
The first line contains an integer 'T', which denotes the number of test cases.
For every test case:-
The first line contains only one integer 'N' the number of cakes.
The second line contains 'N' space-separated strings denoting the elements of the 'S'.
Output Format:- 
For each test case, return the number of ways to choose three cakes irrespective of the order.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints:- 
1 <= 'T' <= 10
1 <= 'N' <= 10^4
0 <= |S[i]| <= 10
All the names of cakes are distinct and consist of lowercase letters.

Time Limit: 1 sec
Sample Input 1:-
2
4
apple kesar strawberry peach
2
apple kesar
Sample Output 1:-
1
0
Explanation of sample input 1:-
'N' = 4, S = ["apple", "kesar", "strawberry", "peach"].
There exists only one way to choose three cakes following all the required conditions i.e. {"strawberry", "apple", "kesar"}. So, the answer is 1.

Second test case:-
'N' = 2, S = ["apple", "kesar"]. As 'N' is less than 3, So there is no way to choose the three cakes. Hence, the answer is 0.
Sample Input 2:-
2
5
apple kesar strawberry peach almond
1
apple
Sample Output 2:-
2
0
Hint

When choosing 3 cakes, there are no more than 10 patterns of the first character of those names.

Approaches (1)
Greedy

 Approach:-

 

Let's first find the frequency of the number of cakes starting with the letters 'c', 'a', 'k', 'e', or 's' each.  Now when choosing 3 cakes, there are no more than 10 patterns of the first character of those names. Let f('x') denote the number of cakes that begin with the character 'x'. The number of ways to choose cakes such that the name begins with 'c', 'a' and 'k' will be f('c') * f('a') * f('k'). So we just need to compute the answer for each of the 10 patterns, this can be achieved using three pointers.

 

 Algorithm:-

 

  • Initialise a vector 'freq' of 64-bit integers to store the frequency of cakes.
  • Iterate from 'i' = 0 to 'N'-1.
    • If the first letter of 'i'th cake is 'c'
      • Increment 'freq[0]' by 1.
    • If the first letter of 'i'th cake is 'a'
      • Increment 'freq[1]' by 1.
    • If the first letter of 'i'th cake is 'k'
      • Increment 'freq[2]' by 1.
    • If the first letter of 'i'th cake is 'c'
      • Increment 'freq[3]' by 1.
    • If the first letter of 'i'th cake is 'c'
      • Increment 'freq[4]' by 1.
  • Initialise an integer 'ans' to store the answer.
  • Iterate from 'i' = 0 to 3.
    • Iterate from 'j' = 'i + 1' to 4.
      • Iterate from 'k' = 'j + 1' to 5.
        • Increment ans by freq[i] * freq[j] * freq[k].
  • Return ans.
Time Complexity

O(N). Where 'N' is the total number of cakes.

Since we are iterating over all the elements once therefore the time complexity will be O(N). Therefore the time complexity will be O(N).

Space Complexity

O(1).             

Since, we are using constant extra space. Therefore, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Cakes
Full screen
Console