bit-manipulation:

Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Example 1: Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. Example 2: Input: 1 Output: 0 Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0.

by lek tin in "algorithm" access_time 2-min read

Bitwise and of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Example 1 Input: [5,7] Output: 4 Example 2 Input: [0,1] Output: 0 Solution «««< HEAD Java class Solution { public int rangeBitwiseAnd(int m, int n) { int shift = 0; while (m < n) { m >>= 1; n >>= 1; shift++; // System.out.println("m: " + String.

by lek tin in "algorithm" access_time 1-min read

Maximum Xor of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231. Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime? Example Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28. Solution (prefix hashset - less efficient) Time: O(N) Space: O(1) class Solution: def findMaximumXOR(self, nums: List[int]) -> int: # 0bxxxxxx - 0b L = len(bin(max(nums))) - 2 max_xor = 0 for i in range(L-1, -1, -1): max_xor <<= 1 print("max_xor:", bin(max_xor) ) # set the rightmost bit to 1 curr_xor = max_xor | 1 print("curr_xor:", bin(curr_xor) ) # highest (L-i) bits prefixes = {num >> i for num in nums} print("prefixes:", [bin(p) for p in prefixes] ) # as long as there exists a p that makes curr_xor^p > 0 # Update max_xor, if two of these prefixes could result in curr_xor.

by lek tin in "algorithm" access_time 2-min read

Utf 8 Validation

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules: For 1-byte character, the first bit is a 0, followed by its unicode code. For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10. This is how the UTF-8 encoding would work: Char. number range | UTF-8 octet sequence (hexadecimal) | (binary) --------------------+--------------------------------------------- 0000 0000-0000 007F | 0xxxxxxx 0000 0080-0000 07FF | 110xxxxx 10xxxxxx 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

by lek tin in "algorithm" access_time 2-min read

Prison Cells After N Days

There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules: If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied. Otherwise, it becomes vacant. (Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.

by lek tin in "algorithm" access_time 3-min read

Power of Two

Given an integer, write a function to determine if it is a power of two. Example 1 Input: 1 Output: true Explanation: 2**0 = 1 Example 2 Input: 16 Output: true Explanation: 2**4 = 16 Example 3 Input: 218 Output: false Solution class Solution: def isPowerOfTwo(self, n): """ :type n: int :rtype: bool """ if n == 0: return False if n & (n - 1) == 0: return True return False

by lek tin in "algorithm" access_time 1-min read

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5]. Note The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity.

by lek tin in "algorithm" access_time 1-min read

Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1 Input: [2,2,3,2] Output: 3 Example 2 Input: [0,1,0,1,0,1,99] Output: 99 Solution class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ # https://www.cnblogs.com/ganganloveu/p/4110996.html # https://blog.csdn.net/karen0310/article/details/78226261 ones, twos = 0, 0 for _, num in enumerate(nums): ones = (ones ^ num) & ~twos twos = (twos ^ num) & ~ones print(bin(num), "ones: ", bin(ones), "twos: ", bin(twos)) return ones

by lek tin in "algorithm" access_time 1-min read

Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1 Input: [2,2,1] Output: 1 Example 2 Input: [4,1,2,1,2] Output: 4 Solution // Java class Solution { public int singleNumber(int[] nums) { int result=0; for(int num : nums) { result=result^num; } return result; } } Solution class Solution: def singleNumber(self, nums: List[int]) -> int: singleNum = nums[0] for i in range(1, len(nums)): singleNum ^= nums[i] return singleNum

by lek tin in "algorithm" access_time 1-min read