HackerRank week of code 32 competition: GeometrickTrick

Question

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.

Answer 1

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