JavaScript solution with explanation (dynamic programming)


  • 2
    K
    /*
    Explanation: 
    It can be build using dynamic programming:
    Sqrt    Sqr
    1       1   
        3
    2       4   = 3 + 1
        5
    3       9   = 5 + 4
        7
    4       16  = 9 + 7
        9
    5       25  = 16 + 9
        11
    6       36  = 25 + 11
        13
    7       49  = 36 + 13
        15
    8       64  = 49 + 15
        17
    9       81  = 64 + 17
        19
    10      100 = 81 + 19
    */
    var isPerfectSquare = function(num) {
      var start = 1;
      var curr = 1;
      var tmp;
      
      if(num === 1){
        return true;
      }
      
      while(curr <= num){
        start += 2;
        tmp = start + curr;
        if (tmp <= num){
          curr = tmp;
          if(curr === num){
              return true;
          }
        } else{
          return false;
        }
      }
      
    };
    

  • 0
    Y

    Based on your idea, I write a shorter one:)

      if(num === 1) return true;
      var add = 3;
      var curr = 1;
      while(curr < num) {
      	curr += add;
      	add +=2;
      }
      return curr === num;
    

Log in to reply
 

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