Euler + Mersenne = Fun + Challenge!


  • 4

    I've seen others use a hard-coded list of the first 26 primes, but I find that ugly. My solution instead uses the Euler primes 41, 43, 47, 53, 61, etc computed by n2+n+41 for n in 0..25. And the Mersenne prime 231-1, aka INT_MAX. For example, the key for the string "abcz" is 41*43*47*691 modulo that Mersenne prime. Of course it's not collision-free, but seems pretty good and gets accepted here.

    I challenge you to find two non-anagram strings that have the same key :-). And if you succeed, I'll replace INT_MAX with a 50-bits prime and challenge you again :-D. I'd like to use a larger Mersenne prime, but unfortunately the next larger one is already bad, because it's 261-1 and my Euler prime for 'z' has 10 bits, so I'd get overflows in the multiplication.

    bool isAnagram(string s, string t) {
        return key(s) == key(t);
    }
    
    long key(string s) {
        long result = 1;
        for (char c : s) {
            int n = c - 'a';
            result = result * (n*n + n + 41) % INT_MAX;
        }
        return result;
    }

  • 0
    M

    Just one thing, do not limit your solution scope into English alphabet, JAVA uses Unicode and the test program works for any kind of string, despite that maybe beyond the question.


  • 1
    P

    @StefanPochmann I am a fan of your solutions. They are so unique in their way of approaching a problem. I wish to code like you someday. I have to ask you this. How long did it take for you to get programming skills like these and what resources did you use to get this far?


  • 3

    @pb1771 Been coding on and off for about 23 years. Studying computer science helped, but mostly I solved lots and lots of these problems in coding competitions and on coding websites and also learned from solutions of others. And, well, I spend a lot of time on refining my code. Also, I actively try to do unique stuff. I don't see the point in posting what others have already posted, as that adds nothing to the discussion but only dilutes it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.