[leetcode] 1437. Check If All 1's Are at Least Length K Places Away

Problem

Code1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var kLengthApart = function(nums, k) {
    if (k == 0) return true;
    
    let count = k;
    for (let i = 0; i < nums.length; i++)
        let n = nums[i];
        if (n == 1)
            if (count >= k) count = 0;
            else            return false;
        else 
            count++;
        // console.log(i, n, count);
    
    return true;
};

• Complexity
  Time Complexity = O(N), n iterations
  Space Complexity = O(1), used a cnt variable only

code2 with bit operation

This is another way to solve this problem. It is a good example of using bitwise operation

var kLengthApart = function(nums, k) {
    let x = 0;
    
    // 1 0 0 0 1 0 0 1
    // 1 => << 1 (00) | n (01)
    // 0 => << 1 (010) | n (0100)
    // ...
    // 1 => << 1 (010001000) | n (010001001)
    // x = 137

  for (let n of nums) 
        x = (x << 1) | n;

    
    // when nums = [0, 0, 0] or k = 0
    if (x == 0 || k == 0) return true;
    
    // remove trailing zeros
    // when nums = [0, 1, 1, 0, 0, 0]
    // x = 00000000 00000000 00000000 00011000
    // 1 = 00000000 00000000 00000000 00000001
    //     000000 and bit operation
    while ((x & 1) == 0) 
        x = x >> 1;
    

	// when you meet last 1 stop loop    
  	// ex) 001000 => 001
    while (x != 1)
    {
        // remove trailing 1-bit
        x = x >> 1;
        
        // count trailing zeros
        let count = 0;

      	// with next 1, (x & 1)
      	// 011001 & 000001 == 1 != 0, stop loop
        while ((x & 1) == 0)
        {
            x = x >> 1;
            ++count;
        }
        
        // number of zeros in-between 1-bits
        // should be greater than or equal to k
        if (count < k)
            return false;
        
    }
    
    return true;
    
};

• Complexity
  Same above