Java coding practice problems – prime and powerful

There is no other way to pass the Java coding tests other than practicing. I have failed Java coding tests due to lack of practice. How often do you get work with tree and graph data structures? Ho often do you work with algorithms?

50+ Java coding practice problems Links:

Can you write code in Java? | Designing your classes & interfaces in Java | Java Data Structures & Algorithms | Passing the unit tests | What is wrong with this code?

Q1. Can you write code to check if a given number is prime?
A1. A prime number is a number that is divisible only by itself and of course 1.

More facts about prime numbers

  • 1 is not a prime number. Prime numbers start from 2
  • 2 is the first and only even prime number
  • all the other prime numbers apart from 2 are odd numbers starting from 3. E.g. 3, 5, 7

A naive solution

Q. What is wrong with the above solution?
A. It is not optimal. if the number is 97, you will end up dividing 97 by from 3 to 96. Goes through the loop 93 times.

A better solution

Two improvements can be made

1) Instead of i++, do i+2, to check for only odd numbers as 2 is the only even prime number. All the others are odd
2) Instead of i < number, do i*i < number because if you look at factors of 99, the factors are repeated half way mark

You can see repeated factors –> 9 * 11 and 11 * 9, 3 * 33 and 33 * 3, etc. So, the revised solution will take advantage of this finding. So, for 97, it will only loop through 4 times for numbers 3, 5, 7, 9. When it gets to 11, it exits the loop as 11 * 11 = 121 which is > 97.

Another more effective approach for isPrime(int number) is:

Q2. Can you write a method that gives a list of prime numbers within a given range?
A2. The range will be supplied via “from” and “to”.

Output:

Q3. Can you list “powerful numbers” between a given range, where the definition of a powerful number is — A positive integer m which is for everyp” that divides “m”, “p*p” must also divide m, where “p” is a prime number

The powerful numbers from 1 to 40 are: 1, 4, 8, 9, 16, 25, 27, 32, 36, …

12 is not a powerful number because: 3 divides 12 but 3*3=9 does not.
18 is not a powerful number because: 2 divides 18, but 2*2=4 does not.
1 is a powerful number because: neither p nor p*p divides it.

A3.

Output:

50+ Java coding practice problems Links:

Can you write code in Java? | Designing your classes & interfaces in Java | Java Data Structures & Algorithms | Passing the unit tests | What is wrong with this code?


300+ Java & Big Data Interview FAQs

16+ Java Key Areas Interview Q&As

800+ Java Interview Q&As

300+ Java & Big Data Tutorials