Posts tagged as “bit”

花花酱 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target

By zxi on July 19, 2020

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.

Example 1:

Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

Example 2:

Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

Example 3:

Input: arr = [1,2,4,8,16], target = 0
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

Solution: Brute Force w/ Optimization

Try all possible [l, r] range with pruning.
1. for a given l, we extend r, since s & x <= s, if s becomes less than target, we can stop the inner loop.
2. Case 1, s = arr[l] & … & arr[n-1], s > target,
Let s’ = arr[l+1] & … & arr[n-1], s’ >= s,
if s > target, then s’ > target, we can stop outer loop as well.
Case 2, inner loop stops at r, s = arr[l] & … & arr[r], s <= target, we continue with l+1.

Time complexity: O(n)? on average, O(n^2) in worst case.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int closestToTarget(vector<int>& arr, int target) {

const int n = arr.size();

int ans = INT_MAX;

for (int i = 0; i < n; ++i) {

int s = arr[i];

for (int j = i; j < n; ++j) {

s &= arr[j];

ans = min(ans, abs(s - target));

if (ans == 0) return 0;

if (s <= target) break; // s is decreasing.

}

if (s > target) break; // s is increasing.

}

return ans;

}

};

花花酱 LeetCode 1483. Kth Ancestor of a Tree Node

By zxi on June 15, 2020

You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.

Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.

The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

Example:

Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:

[null,1,0,-1]

Explanation: TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3 treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5 treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

Constraints:

1 <= k <= n <= 5*10^4
parent[0] == -1 indicating that 0 is the root node.
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5*10^4 queries.

Solution: LogN ancestors

Build the tree from parent array
Traverse the tree
For each node stores up to logn ancestros, 2^0-th, 2^1-th, 2^2-th, …

When k comes in, each node take the highest bit h out, and query its 2^h’s ancestors with k <- (k – 2^h). There will be at most logk recursive query. When it ends? k == 0, we found the ancestors which is the current node. Or node == 0 and k > 0, we already at root which doesn’t have any ancestors so return -1.

Time complexity:
Construction: O(nlogn)
Query: O(logk)

Space complexity:
O(nlogn)

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent):

g_(n), a_(n) {

for (int i = 1; i < n; ++i) g_[parent[i]].push_back(i);

vector<int> path;

dfs(0, path);

}

int getKthAncestor(int node, int k) {

if (k == 0) return node;

if (node == 0 && k > 0) return -1;

int l = min(31ul - __builtin_clz(k), a_[node].size() - 1);

return getKthAncestor(a_[node][l], k - (1 << l));

}

private:

vector<vector<int>> g_, a_;

void dfs(int node, vector<int>& path) {

for (int i = 1; i <= path.size(); i *= 2)

a_[node].push_back(path[path.size() - i]);

path.push_back(node);

for (int c : g_[node]) dfs(c, path);

path.pop_back();

}

};

DP method

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent):

max_level_(32 - __builtin_clz(n)),

dp_(max_level_, vector<int>(n)) {

dp_[0] = parent;

for (int i = 1; i < max_level_; ++i)

for (int j = 0; j < n; ++j)

dp_[i][j] = dp_[i - 1][j] == -1 ? -1 : dp_[i - 1][dp_[i - 1][j]];

}

int getKthAncestor(int node, int k) {

for (int i = 0; i < max_level_ && node != -1; ++i)

if (k & (1 << i))

node = dp_[i][node];

return node;

}

private:

const int max_level_;

vector<vector<int>> dp_;

};

Solution 2: Binary Search

credit: Ziwu Zhou

Construction: O(n)

Traverse the tree in post order, for each node record its depth and id (visiting order).
For each depth, store all the nodes and their ids.

Query: O(logn)

Get the depth and id of the node, if k > d, return -1.
Use binary search to find the first node at depth[d – k] that has a id greater than the query’s one That node is the k-th ancestor of the node.

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent): g_(n), nodes_(n), levels_(n) {

for (int i = 1; i < n; ++i)

g_[parent[i]].push_back(i);

int id = 0;

dfs(0, 0, id);

}

int getKthAncestor(int node, int k) {

const auto [d, id] = nodes_[node];

if (k > d) return -1;

const auto& ns = levels_[d - k];

return upper_bound(begin(ns), end(ns), pair{id, -1})->second;

}

private:

void dfs(int node, int depth, int& id) {

for (int c : g_[node]) dfs(c, depth + 1, ++id);

levels_[depth].emplace_back(id, node);

nodes_[node] = {depth, id};

}

vector<vector<int>> g_; // p -> {{child}}

vector<vector<pair<int, int>>> levels_; // depth -> {{id, node}}

vector<pair<int, int>> nodes_; // node -> {depth, id}

};

花花酱 LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

By zxi on April 5, 2020

Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.

It’s guaranteed that you can always reach to one for all testcases.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.

Example 3:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters ‘0’ or ‘1’
s[0] == '1'

Solution: Simulation

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numSteps(string s) {

int ans = 0;

int carry = 0;

// The highest bit must be 1,

// process to the 2nd highest bit

for (int i = s.length() - 1; i > 0; --i) {

if (s[i] - '0' + carry == 1) {

ans += 2; // odd: +1, even: / 2

carry = 1; // always has a carry

} else {

ans += 1; // even: / 2

// carray remains e.g. 1 + 1 = 10, or 0 + 0 = 00

}

// If there is a carry, then it's even, one more step.

return ans + carry;

}

};

Python3

# Author: Huahua

class Solution:

def numSteps(self, s: str) -> int:

ans, carry = 0, 0

for i in range(1, len(s)):

if ord(s[-i]) - ord('0') + carry == 1:

ans += 2

carry = 1

else:

ans += 1

return ans + carry

花花酱 LeetCode 1386. Cinema Seat Allocation

By zxi on March 22, 2020

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i]=[3,8] means the seat located in row 3 and labelled with 8 is already reserved.

Return the maximum number of four-person families you can allocate on the cinema seats. A four-person family occupies fours seats in one row, that are next to each other. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case, exactly two people have to sit on each side of the aisle.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four families, where seats mark with blue are already reserved and contiguous seats mark with orange are for one family.

Example 2:

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2

Example 3:

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Constraints:

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
All reservedSeats[i] are distinct.

Solution: HashTable + Greedy

if both seat[2~5] seat[6~9] are empty, seat two groups.
if any of seat[2~5] seat[4~7] seat[6~9] is empty seat one group.
if there is no one sit in a row, seat two groups.

Time complexity: O(|reservedSeats|)
Space complexity: O(|rows|)

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {

unordered_map<int, int> rows;

for (auto& seat : reservedSeats)

rows[seat[0]] |= 1 << (seat[1] - 1);

int ans = (n - rows.size()) * 2;

for (const auto& [idx, row] : rows) {

int s2 = row & 0b0000011110;

int s4 = row & 0b0001111000;

int s6 = row & 0b0111100000;

if (s2 == 0 && s6 == 0)

ans += 2;

else if (s2 == 0 || s4 == 0 || s6 == 0)

ans += 1;

}

return ans;

}

};

花花酱 LeetCode 393. UTF-8 Validation

By zxi on March 20, 2020

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.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.

Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

Solution: Bit Operation

Check the first byte of a character and find out the number of bytes (from 0 to 3) left to check. The left bytes must start with 0b10.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool validUtf8(vector<int>& data) {

int left = 0;

for (int d : data) {

if (left == 0) {

if ((d >> 3) == 0b11110) left = 3;

else if ((d >> 4) == 0b1110) left = 2;

else if ((d >> 5) == 0b110) left = 1;

else if ((d >> 7) == 0b0) left = 0;

else return false;

} else {

if ((d >> 6) != 0b10) return false;

--left;

}

return left == 0;

}

};