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.
Loading...
  1. Practice
  2. Algorithms
  3. Strings
  4. Gemstones
  5. Discussions

Gemstones

  • mimibar + 4 comments

    anyone else used bitwise AND?

    • 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 + 0 comments
            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;
        • 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.

    • hkhoi_coder + 2 comments

      Java BitSet makes it easier :)

      • off99555 + 0 comments

        Both C++'s bitset and Java's BitSet are similar. C++ performs better, you need to write less code because it supports operator overloading. But Java's library is always supporting more functionality even though you are writing more code. There are many functions added into Java BitSet. So, they are kind of cancel out when choosing what language to use.

      • Tannia + 1 comment

        How to do it using Java BitSet?..I am curious as I want to learn new java techniques

        • Joshua16163203 + 1 comment

          Its quite easy to use, just imagine it as a string that can only contain '0' and '1' characters. You can use set(int index) to set a specific bit from 0 to 1, use get() to return either true or false depending on whether its set or not and other functions like AND to perform operations with more BitSet objects. I would recommend looking at bit-wise operations (&, |, ^, ~), as well as its API: https://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html.

          Here was my code for the question using BitSet in Java:

          import java.util.Scanner;
import java.util.BitSet;

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int testCases = Integer.parseInt(scanner.nextLine());
    String word = scanner.nextLine().toLowerCase();

    BitSet bits = new BitSet(26);
    BitSet tempBits = new BitSet(26);

    //Populate initial bit set(otherwise it'll XOR with 0 bits)
    for (int i = 0; i < word.length(); i++) {
        //minus 'a' to get it in the range on 0 - 25 (ASCII)
        bits.set(word.charAt(i) - 'a');
    }

    //Loop through remaining words
    for (int i = 1; i < testCases; i++) {
        word = scanner.nextLine().toLowerCase();
        for (int j = 0; j < word.length(); j++) {
            tempBits.set(word.charAt(j) - 'a');
        }

        //if both indexes are 1, then the result is 1, else 0
        bits.and(tempBits);
        tempBits.clear(); //Sets all bits to 0
    }

    //Prints number of 1 bits
    System.out.println(bits.cardinality());
}
          • nm1511 + 0 comments

            Thanks! I had the same general idea at first, but didn't think to use two BitSets...that's why I trashed it and tried for an array increment algorithm that ended up not working out...

    • evanplaice + 0 comments

      I wish. Bitmap was my first thought but I'm wrote my answer in Javascript.

      I char per bit, so bitwise AND per char. Then bitwise AND the sets.

      Not just efficient but much more simple/straighforward.

    • hachimaki1 + 0 comments

      I did. Here's my solution:

      int gemstones(vector <string> arr){
    unsigned int charbits = 4294967295;
    for (string s : arr) {
        unsigned int temp = 0;
        for (char c : s)
            temp |= 1 << (c-'a');
        charbits &= temp;
    }
    return __builtin_popcount(charbits);
}