Shreyansh Makwana Shreyansh Makwana - 1 month ago 6
Java Question

This program take lot of time for execution

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int t = in.nextInt();
if(t<1 || t>100){System.exit(0);}
ArrayList a=new ArrayList<>();
for(int i=0;i<t;i++){
String s=in.next().toString();
String s2=in.next().toString();
int count=0;
int first=Integer.parseInt(s);
int last=Integer.parseInt(s2);
if(first<1 || last>1000000000){System.exit(0);}
for(int k=first;k<=last;k++){
int sqrt =(int)Math.sqrt(k);
if(sqrt*sqrt==k){count++;}
}
a.add(count);
}
Iterator it=a.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}


In this program when i give big input, it takes lots of time to give output. Can someone tell me how to optimize this program.
this program is for finding square root number.
Input: The first line contains , the number of test cases T. T test cases follow, each in a new line.
Each test case contains two space-separated integers denoting s and s2.

Sample Input

2
3 9
17 24


Sample output

2
0


big input:

35
465868129 988379794
181510012 293922871
395151610 407596310
481403421 520201871
309804254 776824625
304742289 566848910
267554756 828997506
387224568 926504395
244571677 871603971
444567315 582147918
334350264 342469009
400474096 410940967
488907300 943628573
26441071 801576263
182001128 267557939
115732998 974318256
192538332 862327048
45429427 307805497
358658006 842644090
92930998 431601473
231163983 893672132
275221547 298953978
351237326 981399371
484598992 985428966
103405553 529324202
37393469 768655346
30179914 482808626
208821550 538302223
154654533 791652309
68424067 854065374
246956110 517538724
51395253 876949418
57778758 368742600
227566632 606529208

Answer

This method compute the number of square between two bounds:

public static int squaredNumberInRange(int lowerBound, int upperBound){
    double lowerRoot = Math.sqrt(lowerBound);
    double upperRoot = Math.sqrt(upperBound);

    lowerRoot = Math.ceil(lowerRoot);
    upperRoot = Math.floor(upperRoot);

    int spread = (int)upperRoot - (int)lowerRoot + 1;

    return spread;
}

Complexity is O(1)