Win a copy of Classic Computer Science Problems in Swift this week in the iOS forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Hackerrank challenge

Ranch Hand
Posts: 116
10
Good morning guys and gals!
I've been away for a bit but i'm returning with a pled for some help...

I did a challenge in Hackerrank and i'm having some problems with timeouts...

The problem there is this one: Project Euler #176: Rectangular triangles that share a cathetus.
It's a programming version of Problem 176 from projecteuler.net.

After some research i found this integer sequence that gives the required number of rectangular triangles wich share a cathetus. If you see there in the FORMULA section, we can get this sequence using the Tau function (also known as Divisor Function). After this i needed a way to count the divisors of a given number and found this page at mathschallenge.net. I used this method in my code.

So the code is:

I used long varibles since the numbers can exceed the Integer maximum value.
The commented lines in my code are the ones needed in Hackerrank to get the input values. I left them just for reference and hardcoded the number of tests (line 7) and the number of triangles (line 12) for testing purposes.

This code works fine. If you run it like it is, it gives the correct answer for the cathetus that is in 4 rectangular triangles (12). The problem is that there can be many tests and numbers can get very large and, therefore, i'm geting timeouts.

I think that the main situation here is that for every test i'm computing the Tau sequence from the start. So i thought that it could help if i memorized all the sequence elements allready computed and, in every next test, only compute the next ones if the answer wasn't found in the allready computed.

What do you think? Should i use an ArrayList since a common Array has fixed length?
Are there any other improvements that can be made?

Best regards
Carlos

Marshal
Posts: 58828
179
Well done getting that far and for all the searches you have done. I think your effort so far merits recognition.

Is that conceptually a pure function with no side‑effects? If so, it is reasonable to make all methods static. Or is there some piece of information linked to several sizes of triangle, in which case you sh‍ould maybe consider an object solution. I think you shou‍ld move all that code out of the main method, anyway. Consider making the methods smaller, but more of them. Have a look at the loop in lines 17‑34. That looks complicated, but I think it can be simplified. You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

Is there a faster way of finding τ0 than a linear search? What is that about prime numbers in the integer list link you gave us? Why are you specifying a particular kind of List? I would have thought that a List was better than an array for most things, but I'll let you work out the details for yourself.  Yes, there is no point in working out the same numbers twice, but please work out why a List would be a better store for numbers than something like a Map.

Note how choice of names for booleans makes the loop hard to read; it would be easier to read with needsFinding instead of notFound.
Are you sure that all numbers will fit within the bounds of a long? What about τ0, which looks a bit like a factorial. Do you need a BigInteger object to handle those numbers?

Carlos Reves
Ranch Hand
Posts: 116
10

Campbell Ritchie wrote:Well done getting that far and for all the searches you have done. I think your effort so far merits recognition.

Thanks for the cow Campbell. Appreciate it!
Many questions here... I'll try to answer...

Campbell Ritchie wrote:Is that conceptually a pure function with no side-effects? If so, it is reasonable to make all methods static. Or is there some piece of information linked to several sizes of triangle, in which case you should maybe consider an object solution.

The choice of having the methods static is not mine. It's the way Hackerranks works internally. I can't change the class name (must be Solution) and since main is given as static, so the methods must be otherwise it won't compile in the site.

Campbell Ritchie wrote:I think you should move all that code out of the main method, anyway. Consider making the methods smaller, but more of them.

The main purpose there isn't the "beauty" of the code but the results. I agree with you though. By the way, will this type of changes affect the speed? (newbie question ).

Campbell Ritchie wrote:Have a look at the loop in lines 17-34. That looks complicated, but I think it can be simplified. You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

It's a bit complicate yes. But it's due to the way we get the values in the sequence. It's different for odd and even numbers. But i'll think about ways of simplifying it.

Campbell Ritchie wrote:You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

Thanks for the info. Now that you mention it, makes sense that a bit manipulation would be faster than a remainder operation...

Campbell Ritchie wrote:Is there a faster way of finding τ0 than a linear search?

If there is than didn't find it yet... Must think about it.

Campbell Ritchie wrote:What is that about prime numbers in the integer list link you gave us?

This one i didn't understand... What prime numbers? I use prime factorization in τ0 yes. But i did that cause i think it is faster than finding the divisors using the brute force remainder opperation from 2 to sqrt() of the number... Other than that i don't see any other primes... Of course it would be good and faster if i simply assigned divisors = 2 if the number is prime... But that would mean that i would need to test the number to see if it is prime... And that means calculating the divisors again...

Campbell Ritchie wrote:Why are you specifying a particular kind of List? I would have thought that a List was better than an array for most things, but I'll let you work out the details for yourself.  Yes, there is no point in working out the same numbers twice, but please work out why a List would be a better store for numbers than something like a Map.

I didn't even consider using a Map. I can use the indexes of the List or ArrayList or Array (whatever i use) to indicate the original number and the corresponding entry as the number of divisors...
I talked about an ArrayList because i assumed (maybe wrong) that it creates a List... Isn't ArrayList an interface? Can't we declare it like this:

Campbell Ritchie wrote:Note how choice of names for booleans makes the loop hard to read; it would be easier to read with needsFinding instead of notFound.

The eternal question of variable names...

Campbell Ritchie wrote:Are you sure that all numbers will fit within the bounds of a long? What about τ0, which looks a bit like a factorial. Do you need a BigInteger object to handle those numbers?

Well maybe... Since we need to square the number to calculate τ0 i guess that at some point it will go beyond the limits of long... Honestly i keep getting timeouts before that...
The good thing i can remember about using BigInteger (apart from the limits issue) is its isProbablePrime method... Would speed up the primes fiding i talked before...

Thanks for the insights Campbell!
Best regards
Carlos

Marshal
Posts: 5623
387

Carlos Reves wrote:I can't change the class name (must be Solution) and since main is given as static, so the methods must be otherwise it won't compile in the site.

Liutauras Vilda
Marshal
Posts: 5623
387

Campbell Ritchie wrote:I think you should move all that code out of the main method, anyway. Consider making the methods smaller, but more of them.

Carlos Reves wrote:The main purpose there isn't the "beauty" of the code but the results. I agree with you though. By the way, will this type of changes affect the speed? (newbie question ).

Yeah, but how you can find a places to improve for performance if code is hardly readable? When code will become straightforward and obvious, you could easier spot which steps are might repetitive or not necessary. Always try write readable code and only then start worrying about the performance if that's the concern.

Campbell Ritchie
Marshal
Posts: 58828
179

Carlos Reves wrote:. . . The choice of having the methods static is not mine. . . . I can't change the class name . . .

It is unfortunate when a website forces you into bad style, but you are stuck with it. Obviously written by people who write procedural code

. . . By the way, will this type of changes affect the speed? . . .

Don't know. Probably no difference.

. . . Thanks for the info. . . .

That's a pleasure.

What prime numbers? . . .

In the website about encyclopedia of number sequences, it said something about prime numbers. I didn't read any more

I didn't even consider using a Map.

I don't know whether a Map will help you; it was just an idea which came randomly into my head. But it never does any harm to consider other suggestions.

. . . Isn't ArrayList an interface? Can't we declare it like this:

It is the other way round; List is the interface and ArrayList the class (=implementation). Yes, that is how you create such a List object, but since Java7 you can probably miss out the second occurrence of Integer.

There is an implementation which is a combination between a Map and a List; searching a List like that isn't very fast, but I think there is an optimisation which starts searching from the end if the index sought is large. Since you will probably be looking for the last entry to continue calculations from, that might make the search faster. In both cases, it might be a good idea to specify the capacity of the collection in advance.

. . . isProbablePrime method... Would speed up the primes fiding i talked before...

Thanks for the insights Campbell!
Best regards
Carlos

I had forgotten about the prime number methods. The cow was well merited, I think Good luck with the rest of the project.

Ranch Hand
Posts: 86
18
A bruteforce approach is most likely not able to solve this problem in reasonable time (the number has 47 binary digits*) - the problem can be solved with a mathematical approach (hint: its based on the prime factors of the divisors value).
(*your current implementation would overflow; changing only the tau0 method won't be sufficient as your outer loop iterates from 2 to this number -> runs quite often)

Regarding your current implementation: The tau0 method should not iterate to n but to sqrt(n). Additionally you could use a wheel to reduce the count of numbers to check and thus modulo operations (2er wheel -> 50%, 2x3er wheel = 33%, ...), below a bit faster version with a 2x3 wheel:

Master Rancher
Posts: 2538
87
A very fast algorithm to find the primes of a number is that of Pollard (https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm.

A method that I picked from the internet (http://introcs.cs.princeton.edu/java/99crypto/PollardRho.java.html) and added a little to it is:

Carlos Reves
Ranch Hand
Posts: 116
10
Thanks all for the tips.

I've worked out another version of my code. It's basically the same as before (no performance tweaks) but tried to simplify the code and make it more readable...
And no more static methods... (thanks Liutauras).

Best regards
Carlos