C# O(log n) time Time Limit Exceeded


  • 0
    Y

    Hi,

    here is my C# solution, it got Time Limit Exceeded, can anybody help me to check(same solution will work in javascript):

    /* The isBadVersion API is defined in the parent class VersionControl.

    bool IsBadVersion(int version); */

    public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        
        if(n==0)
        {
            throw new Exception("");
        }
        
        if(n==1)
        {
            if(IsBadVersion(1))
            return 1;
            throw new Exception("");
        }
        
        int left = 1;
        int right = n;
        int middle = 0;
        
        while(left <= right)
        {
            middle = (left + right)/2;
            
            if(IsBadVersion(middle))
            {
                if(!IsBadVersion(middle-1))
                {
                    return middle;
                }
                else
                {
                    right = middle - 1;
                }
            }
            else
            {
                left = middle + 1;
            }
        }
        
        return middle;
      }
     }

  • 0
    T

    "left + right" will overflow if they are very large


  • 0
    Y

    why the "left + right" will overflow? do you mean that right could be int.Max?


  • 0
    T

    Yes. If right = int.Max, it is possible that after the first loop left = int.Max / 2, which causes left + right to overflow


  • 0
    Y

    any idea to fix the Time Limit Exceeded for my code?


  • 0
    Y

    just figure out how to fix the issue:

    need to replace middle = (left + right)/2; with left + ( right-left) / 2; because if left is larger than int.Max/2, this one will overflow.

    /* The isBadVersion API is defined in the parent class VersionControl.
    bool IsBadVersion(int version); */

    public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
    if(n==0)
    {
    throw new Exception("");
    }

        if(n==1)
        {
            if(IsBadVersion(1))
            return 1;
        }
    
        int left = 1;
        int right = n;
        int middle = 0;
    
        while(left <= right)
        {
            middle =left + ( right-left) / 2;    
    		
            if(IsBadVersion(middle))
            {
                if(!IsBadVersion(middle-1))
                {
                    return middle;
                }
                else
                {
                    right = middle - 1;
                }
            }
            else
            {
                left = middle + 1;
            }
        }
    
        throw new Exception("");;
    }
    

    }


Log in to reply
 

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