PROBLEM LINK:
Author: tseccodecell
DIFFICULTY:
Very Easy
PROBLEM:
You are given N cakes, each made from ingredients represented by the letter a to z. You need to find number of ingredients present in all the cakes.
QUICK EXPLANATION:
Maintain a boolean array or bitfield of length 26. Mark the elements corresponding to ingredients present in the first cake true. For the rest of the cakes, mark any ingredient not present in the cake as false.
EXPLANATION:
We need a way to keep track of ingredients present in all previous cakes. We can either use an array of booleans or a bitfield of length 26 for this purpose. Each element of an array or bit in bitfield corresponds to a single element. Begin by marking all elements corresponding to ingredients present in first cake as true (or set the corresponding bits to 1). Now for all remaining cakes, mark all elements corresponding to ingredients not present in the cake as false (or reset the corresponding bits to 0). This can be done by making a temporary array/bitfield for each cake and ANDing it with the original. Finally, calculate the number of true elements/set bits and print it.