Recently a question was asked that solved a hackerrank problem: Counting gems amongst the rocks
The description of the challenge is:
John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase Latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a 'gem-element' if it occurs at least once in each of the rocks.
Given the list of rocks with their compositions, you have to print how many different kinds of gems-elements he has.
Input Format
The first line consists of N, the number of rocks. Each of the next N lines contain rocks’ composition. Each composition consists of small alphabets of English language.
Output Format
Print the number of different kinds of gem-elements he has.
Constraints
\$1 ≤ N ≤ 100\$
Each composition consists of only small Latin letters ('a'-'z'). 1 ≤ Length of each composition ≤ 100
Sample Input
3 abcdde baccd eeabg
Sample Output
2
Explanation
Only "a", "b" are the two kind of gem-elements, since these characters occur in each of the rocks’ composition.
I was in the process of writing an answer when the question was closed because the code in the question was failing to produce the right results.
My recommended solution to the problem is likely quite fast, but it is also relatively complicated. I am sure it can be improved, and simplified.
I have included a simple main method that shows how it can be used, and produces the sample output.
public class GemCounter {
private static final int LETTERCOUNT = 26;
// Start with 1 bit set for each element/letter.
private int gemsSoFar = (1 << LETTERCOUNT) - 1;
public GemCounter() {
// default constructor. Does nothing.
}
public void processRock(final String rock) {
int gotElement = 0; // no bits are set.
for (int i = 0; i < rock.length(); i++) {
int element = rock.charAt(i) - 'a';
if (element >= 0 && element < LETTERCOUNT) {
// bitwise OR the bit that represents the element
gotElement |= 1 << element;
}
}
// only bits that were found in this rock
// and also that have been seen before
// will remain set.
gemsSoFar = gemsSoFar & gotElement;
}
public int getGemCount() {
// count the number of bits that are still set.
return Integer.bitCount(gemsSoFar);
}
public static void main(String[] args) {
String[] rocks = {"abcdde", "baccd", "eeabg"};
GemCounter gemcount = new GemCounter();
for (String rock : rocks) {
gemcount.processRock(rock);
System.out.printf("Processed %s, got %d gems still%n", rock, gemcount.getGemCount());
}
System.out.printf("%d rocks have %d gems%n", rocks.length, gemcount.getGemCount());
}
}
1 << element
isn't necessary; justelement
should suffice. :) \$\endgroup\$