[LeetCode] 861. Score After Flipping Matrix

 Problem: https://leetcode.com/problems/score-after-flipping-matrix/

- To get the maximum possible number, we need to flip all grid[y][0] to '1'.

- Because we did flip to the first column on the first step, the value on the grid[y][x] = 1 if grid[y][x] == grid[y][0]. Flip the values on each column to get as much ones as possible.

Because every row represents a binary number,  grid[y][x] is worth 1 << (COLUMN - x -1) points.

class Solution {
    public int matrixScore(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;
        
        // To get the maximum value, we need to toggle all grid[i][0] to '1'
        // And every grid[i][0] worths 1 << (COLUMN - 1) points
        
        int result = (1 << (COLUMN - 1)) * ROW;
        
        for (int x = 1; x < COLUMN; x++) {
            
            // count of one on current column
            int countOfOne = 0;
            
            for (int y = 0; y < ROW; y++) {
                
                // because we flipped grid[y][0] to 1
                // grid[y][x] will be '1' if it equals to grid[y][0]
                if (grid[y][x] == grid[y][0]) {
                    countOfOne += 1;
                }
            }
                
            int countOfZero = ROW - countOfOne;

            if (countOfZero > countOfOne) {
                // this column has more zeros than ones
                // flip zero to one to get more ones
                countOfOne = countOfZero;
            }

            // every one on this column worths 1 << (COLUMN - x - 1) points
            result += (1 << (COLUMN - x - 1)) * countOfOne;
        }
        
        return result;
        
    }
}

[LeetCode] 371. Sum of Two Integers

 Problem: https://leetcode.com/problems/sum-of-two-integers/

This quiz is a bit of easier to solve with C language.

class Solution {
public:
    int getSum(int a, int b) {
        int c = 0;
        int carry = 0;
        
        for (int i = 0; i < 32; i ++) {
            int aa = (a >> i) & 1;
            int bb = (b >> i) & 1;
            int cc = aa ^ bb ^ carry;
                    
            carry = (aa + bb + carry) / 2;
            c = c | (cc << i);
        }
        
        return c;
    }
};

The Python solution.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        c = 0
        carry = 0    
        
        for i in range(32):
            x = (a >> i) & 1
            y = (b >> i) & 1
           
            z = x ^ y ^ carry
            
            carry = x & y or x & carry or y & carry
            
            c = (z << i) ^ c
        
        return (c ^ 0x80000000) - 0x80000000

[LeetCode] 338. Counting Bits

 Problem : https://leetcode.com/problems/counting-bits/

A naive solution:

Time complexity = O (n * sizeof(integer))  

class Solution:
    def countBits(self, num: int) -> List[int]:
        def helper(n):
            result = 0
            while n:
                result += n & 1
                n >>= 1
            
            return result
        
        return [helper(n) for n in range(num+1)]

A DP solution:

class Solution:
    def countBits(self, num: int) -> List[int]:
        result = [0] * (num + 1)
        if num >= 1:
            result[1] = 1
            
            for i in range(2, num+1):
                if i & 1 == 0:
                    # if i is even number
                    result[i] = result[i//2]
                else:
                    # if i is odd number
                    result[i] = result[i//2] + 1
        
        return result

[LeetCode] 318. Maximum Product of Word Lengths

 Problem : https://leetcode.com/problems/maximum-product-of-word-lengths/

Calculate hash key base on the letters.  Then wordA and wordB have common letter if keyA & keyB != 0

Time Complexity = O ( N ** 2 )

class Solution {
    public int maxProduct(String[] words) {
        final int[] keys = Arrays.stream(words)
            .mapToInt(this::keyOf)
            .toArray();
        
        return IntStream.range(0, words.length)
            .map(i -> maxProductStartsWithWord(i, words, keys))
            .max()
            .orElse(0);
    }
    
    int maxProductStartsWithWord(int i, String[] words, int[] keys) {
        return IntStream.range(i+1, words.length)
                    .filter(j -> (keys[i] & keys[j]) == 0)
                    .map(j -> words[i].length() * words[j].length())
                    .max()
                    .orElse(0);
    }
    
    int keyOf(String word) {
        return word.chars()
            .reduce(0, (key, w) -> key | (1 << (w - 'a')));
    }
}

Edited on 05/31/2022. Replace with Java functional programming style solution.

[LeetCode] 289. Game of Life

 Problem : https://leetcode.com/problems/game-of-life/

Use bit mask to save the next-state on high-order bits.

Time Complexity = O ( M * N )

Space Complexity = O ( 1 )

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        ROW = len(board)
        if ROW == 0: return 
        
        COLUMN = len(board[0])
        if COLUMN == 0: return
        
        def alive(y,x):
            return 0 <= y < ROW and 0 <= x < COLUMN and board[y][x] & 1 == 1
        
        def nextState(y,x):
            aliveCount = 0
            
            for dy in [-1, 0, 1]:
                for dx in [-1, 0, 1]:
                    if dy == 0 and dx == 0:
                        continue
                    
                    if alive(y+dy, x+dx):
                        aliveCount += 1
            
            """
            Any live cell with fewer than two live neighbors dies as if caused by under-population.
            Any live cell with two or three live neighbors lives on to the next generation.
            Any live cell with more than three live neighbors dies, as if by over-population.
            Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
            """
            
            # dead
            nextState = 0
            
            if board[y][x] == 1:
                if aliveCount < 2:
                    # dead
                    pass
                elif 2 <= aliveCount <= 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            else:
                if aliveCount == 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            
            board[y][x] |= nextState
                    
        
        def normalizeState(y,x):
            board[y][x] = 1 if board[y][x] & (1<<3) else 0
        
        for y in range(ROW):
            for x in range(COLUMN):
                nextState(y, x)
        
        for y in range(ROW):
            for x in range(COLUMN):
                normalizeState(y, x)                

[LeetCode] 268. Missing Number

Problem : https://leetcode.com/problems/missing-number/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        memo = set(nums)
        
        for n in nums:
            if n < len(nums) and n + 1 not in memo:
                return n + 1
        
        return 0

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
    
        for i, n in enumerate(nums):
            missing ^= i ^ n
            
        return missing

As it mentioned, the numbers are from 0 to n.

Now we use all of the valid indices [0, n] to XOR with all numbers. The result is the missing number.

[LeetCode] 260. Single Number III

 Problem : https://leetcode.com/problems/single-number-iii/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        return [x[0] for x in filter(lambda x: x[1] == 1, Counter(nums).items())]

Sort first then count numbers solution:

Time complexity = O ( N * LogN )

Space complexity = O ( 1 )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        a = cntA = 0
        b = cntB = 0
        
        for n in nums:
            if cntA == 0:
                a = n
                cntA += 1
            elif a == n:
                cntA -= 1
            elif cntB == 0:
                b = n
                cntB += 1
            elif b == n:
                cntB -= 1
        
        
        return [a, b]

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution {
    public int[] singleNumber(int[] nums) {
        // Since all numbers except A and B appear twice
        // XOR = A ^ B
        int XOR = 0;
        for (int n : nums) {
            XOR ^= n;
        }
        
        // Find the first bit of the XOR from the right where bit == 1.
        // Because XR = A ^ B, this bit is either contribute by A or B.
        int offset = 0;
        while (offset < 32 && (XOR & (1 << offset)) == 0 ) {
            offset += 1;
        }
                
        // Use the bit of 'offset' as a flag to separate the original numbers to 2 groups
        // Group 1 : A, other numbers except B
        // Group 2 : B, other numbers except A
        // A = accumulated xor of numbers in group 1 
        // B = accumulated xor of number in group 2
        int A = 0, B = 0;
        for (int n : nums) {
            if ((n & (1 << offset)) != 0) {
                A ^= n;
            } else {
                B ^= n;
            }
        }
        
        return new int[] {A, B};
    }
}

Assume A and B are the 2 single numbers. Because all other numbers appear exactly twice. 

xor all numbers  =  A ^ B.

Then find the first bit of A ^ B = 1.   This bit is either from A or from B.

Use this bit to split the nums into 2 groups. Group 1 includes A and all other numbers except B. Group 2 includes B and all other numbers except A.

Since in each group there is only one single number,  result of xor all numbers in the group equals to the single number.

Edited on 11/07/2021. Update bit manipulation solution.

Edited on 05/31/2024. Update bit manipulation solution.

[LeetCode] 231. Power of Two

Problem : https://leetcode.com/problems/power-of-two/

Iteration solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        while n > 1:
            if n % 2 != 0:
                return False

            # n = n // 2
            n = n >> 1
           
        return n == 1

Recursion solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 2 == 0 and self.isPowerOfTwo(n >> 1)

Bit manipulate solution:

Time complexity = O ( 1 )

 
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:   
        
        count = 0
        while n > 0 and count <= 1:
            count += n & 1
            n >>= 1
        
        return count == 1

Number may have only one bit equals to 1 if it is power of 2.

With that observation in mind, we have the one liner solution:

n & (n-1) can trim the first '1' bit from right.

n & (n-1) == 0 means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:    
        return n > 0 and (n - 1) & n == 0

n & (-n) can extract the firt '1' bit from right.

n & (-n) == n also means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (-n) == n

Edited on 05/03/2021. Add the one liner solution.

Edited on 11/07/2021. Add the second one liner solution base on bit manipulation.

[LeetCode] 191. Number of 1 Bits

Problem : https://leetcode.com/problems/number-of-1-bits/

An one liner solution:

Time Complexity = O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum([n >> offset & 1 for offset in range(32)])

Use bit manipulate trick to only count '1'

class Solution:
    def hammingWeight(self, n: int) -> int:
        result = 0
        while n:
            result += 1
            n = n & (n-1)
        
        return result

A divide and conquer approach. And use memorization to accelerate. ( The fastest solution. )

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        #000 001 010 011 100 101 110 111
    
        @cache
        def helper(x):
            return helper(x >> 3) + helper(x & 7) if x > 7 else [0, 1, 1, 2, 1, 2, 2, 3][x]
                
        return helper(n)

Edited on 05/04/2021. Add the only count '1' solution.

Edited on 05/04/2021. Add the divide and conquer solution.