We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Strings
  4. Gemstones
  5. Discussions

Gemstones

  • off99555 + 1 comment

    That's the most efficient way to solve it using bit manipulation because low-level techniques are usually fast. If you really care about speed then consider using int as the data holder and use bitwise operation to perform things. But if you want to write code that are easier to read that mimic bitwise then use bitset because there are built-in functions and overloaded operators for it.

    bitset<26> gem, elems;

    gem.set();

    for each c in string {elems.set(c-'a')}

    gem &= elems;

    • mimibar + 2 comments

      Good to know it's an efficient approach! I basically did what you posted, but with awful code that I am too ashamed to show since I didn't know the existance of BitSet. Thanks!

      • sim_astro + 2 comments

        my code works fine, but want to replace the last for-loop in main, that checks the number of bits on in uint32 with some more optimised code?

        basically i used uint32 to store the 26 alphabets. Parse each string and turn ON the corresponding bit in uint32 and return the variable. Which is bitwise-AND with master uint32 variable.

        unsigned int processing (const std::string& str) {
// find out and return the number of 'chars' that 
unsigned int tmp = 0x00000000;
auto endpt = str.end()
for (auto iter = str.begin(); iter != endpt; iter++) {
    int val = 'z' - *iter;
    //cout << "cur val: " << *iter <<" : " << val << endl;
    tmp |= (0x00000001 << val);
}
return tmp;
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */   
int t;
cin >> t;

char master_list[CNT];
unsigned int can = 0xEFFFFFFF;
for (int i=0; i < CNT; i++) master_list[i] = 'x';
int ret = 0;
while (t--) {
    std::string arr;
    cin >> arr;
    //cout << "input: "<< arr << endl;
    can &= processing(arr);
}
//cout << "result: " << hex << can << endl;
// finding number of bits ON in uint32
unsigned int a = 0x00000001;
int count = 0;
for (int i =0; i<32; i++) {
    if ((can & a) != 0) count++;
    a = a << 1;
}
cout << count << endl;
return 0;
}
        • vladimir_s1 + 0 comments

          __builtin_popcount

        • peterkirby + 1 comment
          int numRocks, allRocks = 0xfffffff;
cin >> numRocks;
while (numRocks--) {
    string s;
    cin >> s;
    int thisRock = 0;
    for (char ch : s)
        thisRock |= 1 << (ch - 'a');
    allRocks &= thisRock;
}
cout << __builtin_popcount(allRocks) << endl;
return 0;
          • r2harshal + 0 comments

            Can you please explain this?

      • kknd511 + 1 comment
        static int toInt(String s){
    int r = 0;
    for(char c: s.toCharArray()){
        r = r| (1<<(c-'a'));
    }
    return r;
}
static int getBits(int l){
    int j=0;
    for(int i=0; i< 26; i++){
        if(((1<<i)&l)!=0){
            j++;
        }
    }
    return j;
}
static int gemstones(String[] arr){
    int rs = Integer.MAX_VALUE;
    for(String s: arr){
        rs = rs & toInt(s);
    }
    return getBits(rs);
}
        • sashagavrilov + 1 comment

          to get number of bits one could use Integer.bitCount

          • kknd511 + 0 comments

            Agreed, would be much more efficient than my home made function.