Gemstones

See the original problem on HackerRank.

Solutions

For each possible character, we can check if it’s present in all rocks.

A Python solution by Yuri Valentini.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import sys
from functools import reduce

n = int(input().strip())
rock = []
rock_i = 0
for rock_i in range(n):
   rock_t = str(input().strip())
   rock.append(frozenset(rock_t))
inters = reduce((lambda a,b: a & b), rock)
print(len(inters))

Another one:

1
print(len(set.intersection(*[set(input()) for _ in range(int(input()))])))

Another one in C#:

1
2
3
4
Console.WriteLine(
    Enumerable.Range(0,int.Parse(Console.ReadLine())).
    Select(_ => Console.ReadLine().AsEnumerable()).
    Aggregate(Enumerable.Intersect).Count());

Another one in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int N; cin >> N;
string s;
map<char, vector<int>> occ;
for (auto i=0; i<N; ++i)
{
    cin >> s;
    for (auto c : s)
    {
        if (occ[c].empty() || occ[c].back() != i)
            occ[c].push_back(i);
    }
}
cout << count_if(begin(occ), end(occ), [&](const pair<const char, vector<int>>& p){
   return p.second.size() == N;
});

Alternative solution by Alessandro Pezzato

This read each character from input one by one, only once. It uses two array of length 26, one to flag characters found in a line, the other to count in how many lines each character has been set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int main() {
  int n;
  scanf("%d", &n);
  char c;
  getchar();

  int f[26];
  int e[26];
  memset(f, 0, sizeof(f));

  for (int i = 0; i != n; ++i) {
    memset(e, 0, sizeof(e));

    /* Read all the string once, flag character when found */
    while (1) {
      c = getchar();
      if (c == '\n' || c == EOF) break;
      e[c - 'a'] |= 1;
    }

    /* Increment count of each found character */
    for (int i = 0; i != 26; ++i) {
      f[i] += e[i];
    }
  }

  int count = 0;
  for (int i = 0; i != 26; ++i) {
    count += f[i] == n;
  }

  printf("%d", count);
}
We've worked on this challenge in these gyms: modena  padua  milan 
comments powered by Disqus