Log(n) submission fail(C#)


  • 0

    Here is my solution.

    public class Solution {
        public int MySqrt(int x) {
            if(x==0||x==1) return x;
            if(x<0) return -1;
            
            int lowerLimit =1;
            int upperLimit=x/2;
            int guess =0;
            int count = 0; //To keep track of how many times the while loop executes
            
            while(lowerLimit<=upperLimit)
            {
                guess = lowerLimit+(upperLimit-lowerLimit)/2;
                Console.WriteLine("Count:{0};Range:{1}-{2}; Guess:{3}",++count,lowerLimit,upperLimit,guess);
                if(guess==x/guess) return guess;
                //Too high
                else if (guess>(x/guess)) 
                {
                    upperLimit = guess-1;
                    guess--;
                }
                //Too low
                else 
                {
                    lowerLimit = guess+1;
                }
            }
            return guess;
        }
    }
    

    It exceeds the test limit for test case = 1579205274

    When I tried to run it as a custom testcase, here is my stdout:

    Count:1;Range:1-789602637; Guess:394801319
    Count:2;Range:1-394801318; Guess:197400659
    Count:3;Range:1-197400658; Guess:98700329
    Count:4;Range:1-98700328; Guess:49350164
    Count:5;Range:1-49350163; Guess:24675082
    Count:6;Range:1-24675081; Guess:12337541
    Count:7;Range:1-12337540; Guess:6168770
    Count:8;Range:1-6168769; Guess:3084385
    Count:9;Range:1-3084384; Guess:1542192
    Count:10;Range:1-1542191; Guess:771096
    Count:11;Range:1-771095; Guess:385548
    Count:12;Range:1-385547; Guess:192774
    Count:13;Range:1-192773; Guess:96387
    Count:14;Range:1-96386; Guess:48193
    Count:15;Range:1-48192; Guess:24096
    Count:16;Range:24097-48192; Guess:36144
    Count:17;Range:36145-48192; Guess:42168
    Count:18;Range:36145-42167; Guess:39156
    Count:19;Range:39157-42167; Guess:40662
    Count:20;Range:39157-40661; Guess:39909
    Count:21;Range:39157-39908; Guess:39532
    Count:22;Range:39533-39908; Guess:39720
    Count:23;Range:39721-39908; Guess:39814
    Count:24;Range:39721-39813; Guess:39767
    Count:25;Range:39721-39766; Guess:39743
    Count:26;Range:39721-39742; Guess:39731
    Count:27;Range:39732-39742; Guess:39737
    Count:28;Range:39738-39742; Guess:39740
    Count:29;Range:39738-39739; Guess:39738
    Count:30;Range:39739-39739; Guess:39739
    

    My answer matches the expected output and runs in 49 ms.

    Why is this still failing?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.