Calculating the perfect squares between two given numbers

Question

This code is for calculating the perfect squares between two given numbers. User can add the interval as well like for how many intervals he want to check the perfect squares. For example if user enter 4, it means there are 4 different intervals and after that he will insert the tow number for interval 1, similarly two numbers for interval 2 and respectively 3 and 4. I just want to reduce the execution time

import java.io.*;
import java.util.*;

class node{
    private int a;
    private int b;
    node(int a, int b){
        this.a = a;
        this.b = b;
    }
    int getA(){return a;}
    int getB(){return b;}
}

public class Solution {

    public static void main(String[] args) {

        int size;
        Scanner S1 = new Scanner(System.in);
        size = S1.nextInt();
        node a[] = new node[size];
        for(int i = 0; i<a.length; i++){
        /*int number = S1.nextInt();
        int number2 = S1.nextInt();*/
        a[i] = new node(S1.nextInt(), S1.nextInt());
        }
        int total = 0;
        int sqrt = 0;
        for(int i = 0; i<a.length; i++){
                for(int j = a[i].getA(); j<=a[i].getB(); j++){
                    sqrt = (int) Math.sqrt(j);
                    if(sqrt*sqrt == j) {
                        total++;
                    }
                }
             System.out.println(total);
            total = 0;
        }
        }
}

Answer 1

First things first. You have to organize your code and group functionality into methods. So I would suggest creating a method int[] getPerfectSquaresBetween(int start, int end).

Let's enhance your algorithm. The key idea is to get the square root of the next perfect square number. This can be achieved by ceil the sqrt of the starting point:

int candidate = (int) Math.ceil(Math.sqrt(start));

This variable is the basis for our calculations. All we have to do now is to check if the candidate squared is in the given range.

int square;
while ((square = candidate * candidate) < end) {
  //...
  candidate++;
}

Putting everything together looks like this:

public static int[] getPerfectSquaresBetween(int start, int end) {
  if (start > end || start < 0) {
    throw new IllegalArgumentException();
  }
  int[] perfectSquares = new int[end - start];
  int nr = 0;
  int candidate = (int) Math.ceil(Math.sqrt(start));
  int square;
  while ((square = candidate * candidate) < end) {
    perfectSquares[nr++] = square;
    candidate++;
  }
  return Arrays.copyOf(perfectSquares, nr);
}

Let's check the algorithm: getPerfectSquaresBetween(0, 101) (which completes in microseconds)

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Answer 2

In addition to @Flown's answer addressing the algorithm, I wanted to mention some code style points that will make your code easier to read and more clear.

• Class names are normally written using PascalCase rather than camelCase, so node should be Node. This will help differentiate types from variables in your code.

• a and b are not very good names for the class parameters. min and max or start and end would make more sense.

• S1 is not a good name for the scanner. Since it is taking input from the console, perhaps call it consoleIn instead.

• Node a[] = new node[size]; is also not a good name. Node[] nodes = new Node[size]; would be more clear.

• You left commented-out code from a previous version in one of your loops, that should be removed now that you no longer need it.

• You should space out your operators and values to make expressions (especially for loops) easier to read.

---

From running your code it was not clear what I was supposed to do. Consider adding console output to give instructions to the user for console-based programs.

---

Your code with above applied:

import java.io.*;
import java.util.*;

class Node {
    private int min;
    private int max;
    Node(int min, int max) {
        this.min = min;
        this.max = max;
    }
    int getMin() { return min; }
    int getMax() { return max; }
}

public class Solution {

    public static void main(String[] args) {

        int size;
        Scanner consoleIn = new Scanner(System.in);
        System.out.print("Enter number of pairs to calculate perfect square of: ");
        size = consoleIn.nextInt();
        Node[] nodes = new Node[size];
        for(int i = 0; i < nodes.length; i++){
            System.out.printf("Enter minimum number of pair %d: ", i + 1);
            int min = consoleIn.nextInt();
            System.out.printf("Enter maximum number of pair %d: ", i + 1);
            int max = consoleIn.nextInt();
            nodes[i] = new Node(min, max);
        }
        int total = 0;
        int sqrt = 0;
        for(int i = 0; i < nodes.length; i++) {
            for(int j = nodes[i].getMin(); j <= nodes[i].getMax(); j++) {
                sqrt = (int) Math.sqrt(j);
                if(sqrt * sqrt == j) {
                    total++;
                }
            }
            System.out.printf("The perfect square of pair %d (%d, %d) is %d%n", 
                    i + 1, nodes[i].getMin(), nodes[i].getMax(), total);
            total = 0;
        }
    }
}

Example run: (demo)

Enter number of pairs to calculate perfect square of:  2
Enter minimum number of pair 1:  42
Enter maximum number of pair 1:  99
Enter minimum number of pair 2:  37
Enter maximum number of pair 2:  53
The perfect square of pair 1 (42, 99) is 3
The perfect square of pair 2 (37, 53) is 1