c++ - Not able to figure out how the code can be further optimised -

-

this problem hackerrank , link : https://www.hackerrank.com/challenges/sherlock-and-squares . program below prints count of numbers perfect squares within given range. however, error of time limit exceeded constraints testcases 1 < testcase < 100 , 2 integers in range 1 < number 1 < 10^9, 1 < number2 < 10^9 .

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include<math.h> using namespace std;   int main() { /* enter code here. read input stdin. print output stdout */      int testcase;   cin>>testcase;          //input testcase   while(testcase--)   {        int number1,number2,count=0;        cin>>number1>>number2;                 //input limits        for(int i=number1;i<=number2;i++) //check each number within limits if proper square         {             if(sqrt(i)==floor(sqrt(i)))             count++;         }          cout<<count<<endl; //print total count of numbers  perfect square within limits     } return 0; }

can please tell me how optimize problem further. not able figure out how time complexity can further reduced.

i'm not going code you. :

instead of testing every number, find first perfect square in range. then, increment 1 square root of perfect square. gives next perfect square. repeat until reach upper limit.

expected improvement around order of numbers. if number1 1000, you'll skipping around thousand number @ each step. should pass easily.


Comments

Post a Comment

Popular posts from this blog

Hatching array of circles in AutoCAD using c# -

-
i beginner in autocad plugins .i have created array of circle using following code. now, have hatch circles in array .how that??how hatch circles @ once? moreover, how can return hatch method , use hatch objects.sorry language.thanks in advance. [assembly: commandclass(typeof(beamsection.class1))] namespace beamsection { public class class1 { //class1 obj = new class1(); [commandmethod("beamatsupport")] public void addlightweightpolyline() { // current document , database document acdoc = application.documentmanager.mdiactivedocument; database accurdb = acdoc.database; promptpointresult ppr = acdoc.editor.getpoint("\nselect starting point "); var ucs = acdoc.editor.currentusercoordinatesystem; point3d startingpt = ppr.value.transformby(ucs); list<double> radius = new list<double>(); radius.add(0.5);
Read more

ios - UITEXTFIELD InputView Uipicker not working in swift -

-
hello trying pop uipickerview view programmatically when user clicks on textfield. have tried doesn't doing anything. isn't working. nothing happening when click textfield class userprofiletableviewcontroller: uitableviewcontroller,uitextfielddelegate,uipickerviewdelegate,uipickerviewdatasource { var itempicker: uipickerview! = uipickerview() @iboutlet weak var gendertxtfield: uitextfield! var gender = ["male","female"] override func viewdidload() { super.viewdidload() gendertxtfield.delegate = self itempicker!.delegate = self itempicker!.datasource = self itempicker!.backgroundcolor = uicolor.blackcolor() self.gendertxtfield.inputview = itempicker } func numberofcomponentsinpickerview(pickerview: uipickerview) -> int{ return 1 } // returns # of rows in each component.. func pickerview(pickerview: uipickerview, numberofrowsincomponent component:
Read more

Python Pig Latin Translator -

-
so have been working on @ codecademy.com while trying learn python. don't know if blind , can't see why won't work or what. here's code won't let me use. function print variable if had typed in , print "empty" if didn't type anything. print "welcome english pig latin translator!" original = raw_input("what's name?") if len(original) > 0 print original else print "empty" if len(original) > 0 else the above lines contains syntax errors. try: if len(original) > 0: else: note added colons, ( : ).
Read more