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:

# Ways to optimize your java code ?

Greenhorn
Posts: 9
I want to optimize below code for efficient run time complexity.

The problem statement is: A number is called a "strange prime" if it is a prime number and its sum of digits (reduced to a single digit) is also a prime number. Sum of digits reduced to a single digit means that if the sum of digits have more than 1 digit, we again sum the digits and follow this process till we get a single digit. So if the number is 345181, then its sum of digits (reduced to a single digit) = 3+4+5+1+8+1 = 22 = 2+2 = 4.
Given a number n as input, return the value of the nth strange prime. Note that some strange primes are 2, 3, 5,7,11,23,29 and so on. 29 is a strange prime because it is a prime number and its sum of digits (reduced to a single digit) = 2+9 = 11 = 1+1 = 2 which is a prime number.
nthStrange(2) = 3
nthStrange(8) = 41

My Solution:

Note: Don't use arrays. Don't use built-in functions. Required a raw solution.

Sheriff
Posts: 23451
46
Welcome to the Ranch!

Abhinav Pande wrote:I want to optimize below code for efficient memory and run time complexity.

Efficient memory? I suppose that means you want to minimize the amount of memory used? Seems kind of pointless since the code creates only one object. And anyway it isn't any more efficient to use 1 kilobyte of memory than it is to use 100 kilobytes. Both numbers are trivially small compared to the amount of memory you have available.

And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

Rancher
Posts: 3742
16

Abhinav Pande wrote:I want to optimize below code for efficient memory and run time complexity.

Before doing either of those, it's probably best to get some code that works.
Try calculating the 5th strange prime with your code.

Abhinav Pande
Greenhorn
Posts: 9

Joanne Neal wrote:
Before doing either of those, it's probably best to get some code that works.
Try calculating the 5th strange prime with your code.

code is correct now answer my question!

Paul Clapham
Sheriff
Posts: 23451
46
You need to answer mine first.

Joanne Neal
Rancher
Posts: 3742
16

Abhinav Pande wrote:now answer my question!

Need working code first.
According to your latest code, the 6th strange prime is 13

Ranch Hand
Posts: 99
1

Abhinav Pande wrote:code is correct now answer my question!

Great way to ask for help.

Abhinav Pande
Greenhorn
Posts: 9

Joanne Neal wrote:
Need working code first.
According to your latest code, the 6th strange prime is 13

now its working! thanks for the review

Abhinav Pande
Greenhorn
Posts: 9

Paul Clapham wrote:

And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

http://en.wikipedia.org/wiki/Time_complexity

code written in such way that when it compiles should take less amount of time for program execution i.e. optimal solution
not a feasible one.

Marshal
Posts: 58470
178

Abhinav Pande wrote: . . . code is correct now answer my question!

That is no way to talk to people who are trying to help. Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only. I think that merits an apology.

lowercase baba
Bartender
Posts: 12613
50

Abhinav Pande wrote:

Paul Clapham wrote:
And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

http://en.wikipedia.org/wiki/Time_complexity
code written in such way that when it compiles should take less amount of time for program execution i.e. optimal solution
not a feasible one.

Doing that is really more of an art, not a science. after all, it is possible the "optimal solution" hasn't been figured out yet.

Generally, when one is trying to optimize code, you start by defining requirements. and those should be SPECIFIC. there is almost always a way to make the code run faster, but the law of diminishing returns apply. is it worth it to spend 40 hours coding to save a microsecond? is it then worth it to spend 200 hours coding to save another? etc.

Also, at some point, it becomes cheaper to by bigger/faster hardware to get speed improvements than to improve the code.

Have you figured out what the complexity of your algorithm even is?

Abhinav Pande
Greenhorn
Posts: 9

Campbell Ritchie wrote:

Abhinav Pande wrote: . . . code is correct now answer my question!

That is no way to talk to people who are trying to help. Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only. I think that merits an apology.

I apologize, I didn't mean that actually but you are right

Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only.

It will never happen again. I'll choose my words correctly in the future.

Paul Clapham
Sheriff
Posts: 23451
46
If you want your code to run faster then basically there are two ways to do that: (1) Find the parts of your program which are executed most often and fix the code to execute them less often; (2) Write some different code which runs faster.

To use option (1) you should profile your code. To do that you need your code to run for some time, so finding "strange prime" number 6 isn't a good test. Finding number 6,000 would be better.

To use option (2) you need to do some mathematical thinking about the algorithm you chose (since it's a mathematical problem). For example you could write

instead of what you had. I doubt this would speed up your code much, since your profiling wouldn't have pointed there as the most frequently-run code, but that's the sort of thing to do.

Campbell Ritchie
Marshal
Posts: 58470
178
Apology accepted

Abhinav Pande
Greenhorn
Posts: 9

Campbell Ritchie wrote:Apology accepted

Thank you

Campbell Ritchie
Marshal
Posts: 58470
178
Now, what algorithm were you using for finding primes, and for the sum of digits. The algorithm for finding primes looks as if it will run in quadratic time. There are far better ways to do that, for example the Sieve of Eratosthenes, which I suggest you read about.
Also, you do not need to loo as far as the number to find whether it is prime. Work out what the best value of the loop index m should be.