I have 2 numbers M and N of range, I want to count all perfect squares in this range and that perfect square should have below property.

lets say the perfect square has digits n1,n2,n3,n4, n5 etc then the digits should be like this: n1 < n2 > n3 < n4 > n5 etc

Example:

Input : M = 40, N = 70

Output : 1

Explanation: The perfect squares in the range 40 to 70 are 49 and 64. But only 49 has the proerty where 4 < 9. But for 64, 6 < 4 is false. So output is 1.

Constraints: 1 <= M <= N <= 10¹¹.

This was asked during an interview and I tried the below code that works for some input and fails for some hidden test cases which I don't know.

I have taken code references from this link to find out perfect squares first.

static int perfectSquares(long M, long N) {
    int total = 0;

    // Getting the very first number
    long number = (long) Math.ceil(Math.sqrt(M));

    // First number's square
    long n2 = number * number;

    // Next number is at the difference of
    number = (number * 2)   1;

    // While the perfect squares
    // are from the range
    while ((n2 >= M && n2 <= N)) {

        /** Logic to check if digits of form d1 < d2 > d3 < d4 > d5 etc **/
        long n = n2;
        String s = n   "";
        int a = s.charAt(0) - '0';
        boolean isless = true;
        boolean valid = true;

        for (int i = 1; i < s.length(); i  ) {
            int b = s.charAt(i) - '0';

            if (isless && a > b) {
                valid = false;
                break;
            }
            if (!isless && a < b) {
                valid = false;
                break;
            }
            isless = !isless;
            a = b;
        }

        // Count the valid the perfect square
        if (valid) {
            System.out.println("sq:"   n2);
            total  ;
        }

        // Get the next perfect square
        n2 = n2   number;

        // Next odd number to be added
        number  = 2;
    }
    return total;
}

Is there any bug in my code or otherwise can we reduce the time complexity of this code?

CodePudding user response：

Issue is with the checks for "valid" where simply using >= and <= will fix it.

I ran your code against the full range (1..100000000000) and found an issue early with the series result (your code prints the valid numbers (i got rid of the newline)):

1 4 9 16 25 36 49 121 144 196 361 441 484 576 676 784 1225 1444 1600 1849 1936 2209 2304 2401 2500 2601 2704 2809 2916 3600 3844 3969 4624 4900 5625 5929 6724 6889 7744 8836 14161 15376 16384 17161 18496 19044 19881 25281 26244 28561 29241 29584 35344 36481 49284 57121 58081 58564 66564 67081 68121 69696 77284 110224 110889 111556 120409 121104 121801 122500 131769 133956 140625 144400 150544 154449 160000 160801 161604 162409 164836 165649 172225 173889 174724 180625 182329 184900 186624 190969 191844 193600 198916 220900 230400 232324 240100 250000 260100 270400 273529 275625 277729 280900 291600 294849 295936 330625 332929 342225 351649 352836 360000 361201 362404 363609 364816 374544 375769 381924 384400 390625 396900 442225 443556 444889 452929 455625 462400 471969 481636 484416 485809 490000 491401 492804 495616 553536 562500 565504 571536 580644 586756 592900 660969 665856 672400 680625 683929 688900 692224 693889 695556 774400 777924 786769 883600 894916 896809 1119364 1227664 1229881 1304164 1406596 1418481 1503076 1515361 1527696 1535121 1615441 1623076 1628176 1633284 1666681 1669264 1726596 1745041 1747684 1758276 1766241 1844164 1855044 1907161 1937664 1999396 2208196 2214144 2217121 2223081 2226064 2307361 2316484 2328676 2427364 2446096 2515396 2534464 2637376 2768896 2802276 2819041 2849344 2859481 2917264 2937796 2979076 2989441 3316041 3319684 3334276 3504384 3519376 3538161 3644281 3709476 3717184 3748096 3767481 3837681 3849444 3857296 3888784 3916441 3924361 3944196 3956121 3968064 4528384 4713241 4717584 4726276 4748041 4778596 4879681 4937284 4946176 4955076 4968441 4977361 4999696 5612161 5626384 5645376 5669161 5803281 5827396 5866084 5900041 5934096 5958481 6615184 6625476 6646084 6713281 6718464 6859161 6906384 6922161 6948496 6959044 7706176 7717284 7907344 7918596 7958041 8856576 8868484 8916196 8928144 8934121 8946081 9979281 11022400 11042329 11055625 11088900 11122225 11155600 11175649 11182336 11195716 12040900 12061729 12075625 12110400 12180100 12250000 13010449 13053769 13140625 13176900 13191424 13271449 13293316 13344409 13351716 13373649 13395600 14032516 14040009 14062500 14070001 14092516 14152644 14182756 14197824 14250625 14265729 14386849 14394436 14440000 14462809 14470416 14485636 15054400 15186609 15194404 15233409 15241216 15264649 15342889 15350724 15444900 15460624 15499969 15570916 15586704 15594601 16000000 16080100 16120225 16160400 16184529 16240900 16281225 16353936 16370116 16394401 16483600 16564900 16662724 16670889 17073424 17164449 17172736 17222500 17230801 17255716 17272336 17280649 17355556 17363889 17372224 17388900 17472400 17673616 17690436 17698849 17774656 17791524 18011536 18062500 18164644 18190225 18232900 18275625 18292729 18352656 18361225 18386944 18455616 18472804 18481401 18490000 18662400 18774889 18783556 18792225 18887716 19061956 19096900 19140625 19184400 19254544 19333609 19342404 19351201 19360000 19465744 19492225 19562929 19580625 19686969 19695844 19775809 19784704 19793601 19891600 22033636 22052416 22061809 22071204 22080601 22090000 22155849 22231225 22240656 23011209 23020804 23030401 23040000 23164969 23193856 23232400 23261329 23280625 23299929 24000201 24010000 24176889 24186724 24255625 24373969 24383844 24462916 24472809 24482704 24492601 25000000 25010001 25020004 25030009 25150225 25180324 25230529 25250625 25270729 25351225 25381444 25441936 25472209 25482304 25492401 26010000 26020201 26030404 26040609 26050816 26081449 26132544 26142769 26193924 26265625 26450449 26460736 26481316 26491609 26553409 26563716 26594649 26697889 27040000 27050401 27060804 27071209 27081616 27164944 27352900 27373824 27394756 27562500 27583504 27772900 28090000 28111204 28121809 28132416 28153636 28355625 28376929 28440889 28451556 28462225 28590409 28686736 28793956 28890625 29030544 29084449 29160000 29170801 29181604 29192409 29343889 29354724 29452329 29484900 29560969 29571844 29593600 29680704 29691601 33062500 33085504 33131536 33292900 33350625 33373729 34140649 34152336 34175716 34222500 34292736 34374769 35010889 35022724 35081929 35164900 35283600 35354916 35366809 35390601 35450116 35473936 35485849 35581225 36000000 36120100 36180225 36240400 36360900 36481600 36590401 37063744 37161216 37173409 37185604 37197801 37222201 37454400 37576900 37662769 37773316 37785609 37797904 38031889 38130625 38192400 38241856 38365636 38390416 38440000 38452401 38464804 38588944 38663524 38775529 39050001 39062500 39250225 39262756 39287824 39350529 39375625 39463524 39664804 39690000 39891856 44142736 44182609 44195904 44222500 44262409 44275716 44355600 44462224 44488900 45050944 45091225 45131524 45252529 45292900 45360225 45481536 45562500 46022656 46076944 46144849 46185616 46240000 46253601 46280809 46294416 46553329 46580625 47141956 47196900 47265625 47361924 47444544 47554816 47582404 47692836 47775744 48052624 48121969 48163600 48260809 48274704 48330304 48385936 48441600 48580900 48790225 49000000 49140100 49252324 49280400 49350625 49491225 49561600 49660209 49885969 55011889 55130625 55160329 55353600 55442916 55472704 55591936 56220004 56250000 56280004 56550400 56595529 57032704 57062916 57153600 57183844 57198969 57274624 57350329 57380625 57486724 57577744 57790404 58033924 58064400 58140625 58277956 58461316 58476609 58491904 58583716 58675600 58782889 59043856 59243809 59274601 59290000 59351616 59382436 59397849 59474944 59675625 59783824 66096900 66161956 66373609 66471409 66487716 66585600 66683556 67141636 67174416 67190809 67240000 67272804 67354849 67683529 68062500 68095504 68161536 68260644 68392900 68442529 68475625 68591524 68690944 68773849 68790436 68890000 69155856 69222400 69272329 69388900 69455556 69472225 69555600 69672409 69772609 77000625 77440000 77492809 77792400 78021889 78251716 78340201 78375609 78393316 78552769 78676900 79174404 79192201 79263409 79281216 79691329 79780624 79887844 88021924 88284816 88341201 88360000 88472836 88491649 88585744 88792929 89075844 89264704 89283601 89340304 89491600 89680900 89775625 99022401 99042304 99062209 99121936 99141849 99241444 99460729 110418064 110439081 110502144 110544196 110649361 110838784 111746041 111767184 111809476 111915241 111957561 120209296 120428676 120516484 120538441 120736144 120758121 120802081 120824064 121308196 121418361 121528576 121837444 122412096 122722084 122744241 130439241 130507776 130622041 130919364 131308681 131423296 131744484 131767441 131813361 131928196 132434064 132503121 132526144 132756484 132848676 133726096 133888041 133911184 133957476 140209281 140612164 140707044 140944384 141419664 141824281 142229476 142301041 143328784 143544361 143712144 143736121 143808064 144504441 144528484 150528361 150749284 151807041 151979584 152226244 152819044 152868496 153958464 154405476 154778481 154803364 155725441 160326244 160757041 161518681 161849284 162333081 162766564 162919696 163609681 163635264 164506276 164557584 164814244 165611161 166616464 166978084 170537481 170668096 170877184 170929476 171819664 172423161 172607044 172712164 173659684 173923344 174609796 174927076 175801081 177715561 177848896 177902244 180311184 180338041 180526096 181225444 181548676 181656484 181737361 181926144 182547121 182628196 182817441 182844484 183819364 183846481 184715281 185558884 185613376 185804161 186978276 187909264 187936681 188815081 190219264 190826596 192959881 193738561 193822084 193877776 193989184 194937444 195608196 195748081 196616484 196728676 220879044 220938496 221444161 222427396 222636241 222666084 222845184 230402041 230766481 231709284 232227121 232318564 232806564 232837081 232989696 233417284 233845264 240002064 240529081 240622144 240839361 241118784 241429444 242549476 242705241 242767561 242923396 243609664 244547044 250304041 250525584 250557241 250778896 250937281 251603044 251666496 251825161 252206161 253637476 253701184 253733041 253956096 254849296 255616144 255648121 255712081 255744064 260209161 260435044 261113281 261436561 261727684 263445361 263607696 263705121 264517696 264745441 264908176 266636241 270306481 270339364 271524484 271557441 271623361 272514064 272547081 272613121 272646144 272712196 272877361 273439296 273505444 274929561 275858881 276756496 276823044 276956164 277855561 277922241 277955584 281434176 281769796 281937681 282946041 282979684 283518244 283619281 284968161 285914281 286828096 287709444 287777296 290225296 291419041 291658084 293711044 293848164 294534244 294877584 294946276 296666176 296735076 296838441 296907361 297838564 298978681 330439684 330803344 331749796 332734081 333756361 333829441 333939076 340107364 340845444 340919296 341436484 341547361 341806144 341917081 342546064 342657121 342768196 343657444 343768681 344436481 344622096 344919184 350513284 351225081 351900081 352538176 352613284 353778481 353966596 354418276 354606561 355624164 360544144 360658081 361304064 361418121 361836484 361988676 362445444 362559681 363436096 363703041 363817476 364504464 365536161 365727376 370216081 370909081 371949796 372837481 373301041 373339684 373958244 375623161 376709281 376903396 377758096 380601081 380718144 381108484 381655296 382515364 383337241 383415561 383807281 383846464 384905161 385768881 385808164 386869561 386948241 387735481 388957284 390418081 390813361 391723264 392515344 393546244 394777161 396766561 396846241 440118441 440412196 440538121 440622081 441336064 441504144 441924484 442513296 443439364 444408561 444619396 450755361 450967696 451945081 452668176 453306681 454627684 454926241 460617444 460703296 461218576 461304484 461433361 461648196 461734144 461777121 461906064 462637081 462723121 462766144 464747364 465739561 465955396 466948881 471845284 473889361 474629796 474847681 477947044 480004281 480223396 480749476 480837184 481407481 482329444 482417296 482768784 482856676 483516121 483604081 483648064 484528144 484616196 484836361 484924441 484968484 491908041 492218596 492307344 493817284 493906176 494439696 494706564 495908361 496888681 496933264 497825344 550559296 551216484 551733121 551827081 552626064 552767121 552814144 552908196 554979364 555639184 555827776 555922084 555969241 560316241 560647684 562733284 562828176 562923076 563635081 564727696 566868481 570302161 570779881 570827664 571879396 572214241 572549184 574848576 574944484 575616064 577729296 577825444 577969681 580424464 581726161 581967376 582305161 582546496 582836164 583657281 583802244 584624041 586705284 586802176 590927481 591511041 591559684 592338244 593312164 593507044 593604496 593848161 594433161 594969664 596629476 596727184 598878784 661209796 661724176 661827076 663526081 663629121 664402176 664505284 664917796 666724041 671224464 671535396 672313041 672935481 673869681 674648676 674856484 674908441 676624144 676728196 676988361 677977444 680114241 680218561 681627664 682202161 682829161 683404164 684816561 685706596 685968481 686859264 687803076 690323076 690428176 690533284 691216681 692426596 692847684 693848281 694744164 694955044 695957161 770506564 770839696 771117361 771228441 771506176 771617284 772339681 773507344 773618596 776848384 780755364 782656576 782768484 782824441 782936361 783328144 784448064 784504081 784616121 788823396 790959376 791634496 791747044 792929281 793605241 793999684 795747681 796707076 796989361 880427584 880546276 881555481 883516176 883635076 884408121 884527081 885538564 885717121 886729284 890306244 891559881 891739044 891858496 892336384 894548281 894847396 895745041 990738576 990927441 991557121 991746064 992817081 993447361 993636484 993888676 994519296 994645444 995907364 996728041 996917476

You should see it straight away: 144.

So making the conditional changes as described yields:

1 4 9 16 25 36 49 121 196 361 484 576 676 784 1849 1936 2304 2401 2601 2704 2809 2916 3969 4624 5625 5929 6724 14161 15376 16384 17161 18496 25281 28561 29241 29584 36481 49284 57121 58081 58564 67081 68121 69696 120409 121801 131769 140625 160801 161604 162409 164836 165649 174724 180625 182329 190969 198916 232324 273529 275625 294849 295936 351649 352836 361201 362404 363609 364816 375769 381924 390625 452929 471969 481636 485809 491401 492804 495616 571536 586756 680625 683929 786769 894916 896809 1304164 1406596 1418481 1503076 1515361 1527696 1535121 1623076 1628176 1726596 1745041 1747684 1758276 1907161 2307361 2316484 2328676 2427364 2515396 2637376 2819041 2859481 2917264 2979076 3504384 3519376 3538161 3709476 3717184 3748096 3767481 3837681 3857296 3924361 3956121 3968064 4528384 4713241 4717584 4726276 4748041 4879681 4937284 4946176 5612161 5626384 5645376 5803281 5827396 5934096 5958481 6713281 6718464 6859161 6906384 6948496 7918596 7958041 8916196 8934121 8946081 12061729 12075625 13053769 13140625 13191424 14032516 14092516 14182756 14197824 14250625 14265729 14386849 15241216 15264649 15350724 15460624 16184529 16353936 17073424 17172736 17230801 17280649 17673616 17690436 18275625 18292729 18352656 18472804 18481401 19061956 19140625 19342404 19351201 19562929 19580625 19686969 19784704 19793601 23020804 23030401 23164969 23193856 23261329 23280625 24186724 24373969 25180324 25230529 25250625 25270729 25482304 25492401 26020201 26030404 26040609 26050816 26142769 26193924 26265625 26460736 26481316 26491609 26563716 26594649 27050401 27060804 27071209 27081616 27373824 27394756 27583504 28121809 28132416 28153636 28376929 28590409 28686736 28793956 29170801 29181604 29192409 29354724 29452329 29560969 29680704 29691601 34140649 34175716 34292736 34374769 35081929 35354916 35390601 35473936 35485849 36590401 37161216 37173409 37185604 37197801 38130625 38241856 38365636 38390416 38452401 38464804 39262756 39287824 39350529 39375625 39463524 39891856 45131524 45252529 45481536 46185616 46253601 46280809 46580625 47141956 47265625 47361924 47582404 47692836 48052624 48121969 48260809 48274704 48385936 49252324 49350625 57032704 57062916 57198969 57274624 57350329 57380625 57486724 58140625 58461316 58491904 58583716 59043856 59243809 59274601 59351616 59382436 59397849 59675625 59783824 67141636 67190809 67272804 67354849 67683529 68161536 68475625 68591524 68790436 69272329 69672409 78251716 78340201 78375609 79263409 79281216 79691329 79780624 89264704 89283601 89340304 120209296 120428676 120516484 120758121 120802081 120824064 121308196 121418361 121528576 130439241 130919364 131308681 131423296 131928196 132434064 132503121 132756484 132848676 140209281 140612164 141824281 142301041 143736121 143808064 150528361 150749284 151807041 151979584 152868496 153958464 160757041 161518681 161849284 162919696 163609681 163635264 164506276 170537481 170929476 172423161 172712164 173659684 174609796 174927076 175801081 180526096 181548676 181656484 181737361 182547121 182628196 183819364 183846481 184715281 185804161 186978276 187909264 190219264 190826596 193738561 193989184 195608196 195748081 196728676 230402041 231709284 232318564 232806564 232837081 232989696 240529081 240839361 242549476 242705241 242767561 250304041 250937281 251825161 253637476 253956096 254849296 260209161 261436561 261727684 263607696 263705121 264517696 264908176 270306481 272514064 272547081 272613121 272712196 273439296 274929561 276756496 276956164 281434176 281769796 281937681 282946041 282979684 283619281 284968161 285914281 286828096 291419041 291658084 293848164 294946276 296735076 296907361 297838564 298978681 340107364 340919296 341436484 341547361 341917081 342546064 342657121 342768196 343768681 350513284 352538176 352613284 354606561 360658081 361304064 361418121 361836484 363436096 363703041 363817476 365727376 370216081 370909081 371949796 372837481 375623161 376709281 380601081 382515364 383807281 383846464 384905161 385808164 386869561 386948241 390418081 391723264 396846241 450967696 451945081 454627684 454926241 460703296 461218576 461648196 461906064 462637081 462723121 464747364 465739561 471845284 474629796 474847681 480749476 480837184 481407481 482417296 482768784 483516121 483604081 483648064 484616196 484836361 484968484 491908041 493817284 493906176 494706564 495908361 560316241 560647684 562828176 562923076 563635081 564727696 570302161 571879396 572549184 574848576 575616064 581726161 581967376 582305161 582546496 582836164 583657281 584624041 586705284 586802176 590927481 593848161 596727184 671535396 672313041 672935481 673869681 674648676 674856484 676728196 680218561 682829161 683404164 684816561 685706596 685968481 686859264 687803076 690323076 690428176 692426596 692847684 693848281 695957161 782656576 782768484 782936361 784504081 784616121 790959376 792929281 793605241 795747681 796707076 796989361 891858496 894548281 894847396 895745041

Here's that section of code with the change - I suspect it doesn't need explaining ... but for n1 < n2 then the negation of that check is n1 >= n2 and similarly with n2 > n3 then the negation is n2 <= n3...

if (isless && a >= b) {
    valid = false;
    break;
}
if (!isless && a <= b) {
    valid = false;
    break;
}

Well, I didn't check every number but this correction seems promising, agreed?

CodePudding user response：

Personally, I think you may have over-complicated how to get the squares. Consider the following:

// square root of lowest perfect square in range
int n = (int)(Math.ceil(Math.sqrt(N))); 
// square root of highest perfect square in range
int m = (int)(Math.floor(Math.sqrt(M)));
    
for (int i=n;i<=m;i  )
{
    // Calculate the number to test
    long j = i * i;
    etc...

For more readability, you might also split the order test into its own function. Here is a different implementation that uses math, rather than using strings.

/** Test to see if the given number has all digits in increasing order 
    when read from Most Significant Digit to Least Significant Digit */
private boolean isOrdered(long n)
{
    // Preset our current Least Significant Digit so that the first test
    // won't fail.
    long last = 10;
    
    while (n > 0)
    {
        // Get the least significant digit
        long digit = n % 10;

        // If the digit is greater than or equal to the previous LS digit, 
        //    then return false.
        if (digit >= last)
        {
            return false;
        }
        // Remember the current LS Digit.
        last = digit;
        
        // Move to the next digit.
        n = n / 10;
    }
    return true;
}