4
\$\begingroup\$

last week I entered HackerRank Week of Code 32, a week-long competition, with 6 coding challenges, ranging from easy to hard. I am satisfied with my result at this particular competition but I also would like to understand where I failed.

The competition is over since monday morning so it's not to cheat in the competition that I ask help.

The challenge I'm blocking on his of medium difficulty (says HackerRank competition, I found it hard enough^^).

I would like your advice on how I could improve my code performance-wise.

I'll announce the problem, and then show you what I've done

GEOMETRIC TRICK:

Consider a string \$s\$ of length \$n\$ consisting of the character in the set \$\{a,b,c\}\$. We want to know the number of different \$(i,j,k)\$ triplets (where \$0 \le i,j,k \lt n\$) satisfying two conditions:

  • \$s[i] = “a”, s[j] = “b”, s[k] = “c”\$

  • \$(j + 1)^2 = (i + 1)(k + 1)\$

We consider two triples \$(i,j,k)\$, and \$(x,y,z)\$, to be different if and only if \$i \ne x\$ or \$(j \ne y)\$, or \$(k \ne z)\$.

Given \$n\$ and \$s\$, find and print the number of different \$i,j,k\$ triples. My approach

Example

Given the string "ccaccbbbaccccca" of length 15, the final result is 2.

  • {2,5,11} satisfy both conditions
    • s[2] = 'a', s[5] = 'b' and s[11] = 'c'
    • (5 + 1)² = (2 + 1)(11 + 1)
  • {8,5,3} satisfy both conditions
    • s[8] = 'a', s[5] = 'b' and s[3] = 'c'
    • (5 + 1)² = (8 + 1)(3 + 1)

We find 2 triples that match the 2 conditions so the answer is 2.

The code

gist link = https://gist.github.com/JulienRouse/cafbce417bbc2a4f6303df10df20d445

Code here:

/**
 * Consider a string s of length n with alphabet {a,b,c}.
 * We look for the number of different triplet (i,j,k) where 0<=i,j,k<n, satisfying!
 * - s[i] = "a", s[j] = "b", s[k] = "c"
 * - (j + 1)² = (i + 1)(k + 1) 
 * @param s A string we look the triplet in
 * @return Number of different triplets such as enonced above. 
 */
public static int geometricTrickv2(String s){

    Set<Integer> indexA = new HashSet<>(s.length());
    Set<Integer> indexC = new HashSet<>(s.length());

    List<Integer> indexB = new ArrayList<>();

    for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='a')
            indexA.add(i);
        if(s.charAt(i)=='b')
            indexB.add(i);
        if(s.charAt(i)=='c')
            indexC.add(i);
    }


    int res = 0;
    for(int tmpB:indexB){
        int powB = (int)Math.pow((double)(tmpB+1),2);
        for(int i=2;i<=Math.sqrt((double)powB);i++){
            if(powB%i==0){
                if(i != powB/i)
                    if(indexA.contains(i-1)&&indexC.contains(powB/i-1))
                        res++;
                    if(indexC.contains(i-1)&&indexA.contains(powB/i-1))
                        res++;
                else
                    if(indexA.contains(i-1)&&indexC.contains(i-1))
                        res++;
            }
        }

    }

    return res;

}

Explanation

First thing: I build 2 HashSet with the indexes of the letter 'a' and 'c' and a list of the indexes of the letter 'b' in the string s.

Then, I'll work with the given condition \$(j + 1)^2 = (i + 1)(k + 1)\$, which can be seen as:

  • find i and k such as \$i+1\$ and \$k+1\$ are complementary divisor of \$(j+1)^2\$

(By complementary I mean: say you have 25, his divisors are 1,5 and 25. 1 and 25 are complementary in the way that 1*25 = 25, 5*5=25 but 1*5!=25. so 1 and 25 are complementary, 5 is complementary with himself but (1 and 5) and (5 and 25) are not complementary )

To find all the divisor of n, I only need to search up until sqrt(n). (It's a property I remember from high school, hope I didn't screw up) because I can calculate the divisor and their complementary counterpart on the same iteration.

Then once I am calculating those divisor, I need to check if they are in the HashSet containing the indexes of 'a' and 'c', and satisfying the condition.

Complexity

We say m = number of letters 'b' If I'm not mistaken, complexity is \$O(m \sqrt{m})\$ (For each index of 'b', I compute his divisor in \$\sqrt{m}\$ times and every other operation is \$O(1)\$ or not in the loop)

My problem

When I submitted my code to the challenge, the result where correct when string s was small, but quickly timed out for bigger input. There must be a better solution but I can't find so if anybody got suggestions on algorithms I would greatly appreciate.

Also if you have any tips to give me about code clarity, about problem solving or anything that makes me learn and improve. It will be really great.

Thanks for reading all the way, sorry for my English.

\$\endgroup\$
  • \$\begingroup\$ @Peilonrayz ty for the MathJax formating! \$\endgroup\$ – Julien Rousé May 23 '17 at 15:18
2
\$\begingroup\$

You don't need the HashSets to see if \$s[i] = “a”\$ you only need to do s.chatAt(i) == 'a'. If you really want to minimize the time it takes then dumping it into a char[] would be best.

Something to note is that you can square ints much faster doing the simple multiply with self method than convert to double and use call Math.pow. Also the square root of a square is the same as the original number.

int powB = (tmpB+1)(tmpB+1);
for(int i=2;i < tmpB;i++){
    if(powB%i==0){

\$i, j, k\$ all have to be distinct because the characters they refer to must be different so you can save a few test and iterations there.


The algorithm you have boils down to

for(int j : indexB){
    for(int i : getDividersFor((j+1)(j+1))){
         int k = (j+1)/i - 1;
         i-=1;
         // check if i, j and k have the correct values. 
         // and check for i and k swapped

    }
}

Where getDividersFor(n) has time complexity of \$O(\sqrt n)\$. But because n passed in is the square of j the total complexity is \$O(m^2)\$

Instead given a \$i\$ you can construct a \$k\$ such that \$(i+1)(k+1)\$ is a perfect square.

First you factor \$i+1\$ into prime powers. Then you take all odd prime powers and multiply them together. For example for \$60 = 2^2 * 3^1 * 5^1\$ you multiply 3 and 5 to get 15 as the start value of k and \$15*60 = 900 = 30^2\$.

That is the start value of \$k+1\$ and you multiply it with squares until you go past the end of the string:

for(int i = 0; i < s.length(); i++){
    if(s.charAt(i) != 'a' && s.charAt(i) != 'c')//cannot pass inner check
        continue;

    int k0 = extractOddPrimesAndMultiply(i+1);
    int j0 = (int)Math.sqrt((i+1)*k0) - 1;
    for(int factor = 1; j0*factor - 1 < s.length() && 
                        k0*factor*factor < i+1; factor++){

        int k = k0*factor*factor - 1;
        int j = j0*factor - 1;

        //test string values and check for i and k swapped

    }

}

This actually has \$O(m \sqrt m)\$ complexity

\$\endgroup\$
  • \$\begingroup\$ I can use charAt because String internal is an array right? It's actually a good tip, as I also was wasting lots of memory. Also O(m²) because I square j is a good catch! Totally miss that one. For the algorithm you proposed, your trick for building perfect square out of odd prime factor of another number, is that a known trick? Very cool indeed! Thank you very much, do you think this is the lowest bound for solving this particular problem? \$\endgroup\$ – Julien Rousé May 23 '17 at 16:05
  • \$\begingroup\$ @JulienRousé the trick makes sense when you understand how prime factors and multiplication work. Worst case for the inner loop is when i+1 already is a perfect square, then k0 is 1 and the inner loop runs sqrt(i) times. Though most of the time it's less. \$\endgroup\$ – ratchet freak May 23 '17 at 16:18
  • \$\begingroup\$ Thank you a lot for you very good tips and explanation @ratchet, I guess I need to relearn a bit of math to be more able to solve those problems. \$\endgroup\$ – Julien Rousé May 24 '17 at 6:13
  • \$\begingroup\$ @JulienRousé usually the crucial step for optimizing those kind of problems (like you will notice with project euler problems) is to invert the nested loops using those kind of math tricks to get big O complexity down. \$\endgroup\$ – ratchet freak May 24 '17 at 8:02
  • \$\begingroup\$ Yes I started project euler problems some times ago but often I am really slowed down by my math knowledge and/or algorithmic trick to reduce complexity. \$\endgroup\$ – Julien Rousé May 24 '17 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.