Posts tagged as “bit”

花花酱 LeetCode 421. Maximum XOR of Two Numbers in an Array

By zxi on December 27, 2020

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

1 <= nums.length <= 2 * 10⁴
0 <= nums[i] <= 2³¹ - 1

Solution: Trie

Time complexity: O(31*2*n)
Space complexity: O(31*2*n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children(2) {}

vector<unique_ptr<Trie>> children;

};

class Solution {

public:

int findMaximumXOR(vector<int>& nums) {

Trie root;

// Insert a number into the trie.

auto insert = [&](Trie* node, int num) {

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = std::make_unique<Trie>();

node = node->children[bit].get();

}

};

// Find max xor sum of num and another element in the array.

auto query = [&](Trie* node, int num) {

int sum = 0;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum += (1 << i);

node = node->children[1 - bit].get();

} else {

node = node->children[bit].get();

}

return sum;

};

// Insert all numbers.

for (int x : nums)

insert(&root, x);

int ans = 0;

// For each number find the maximum xor sum.

for (int x : nums)

ans = max(ans, query(&root, x));

return ans;

}

};

花花酱 LeetCode 1649. Create Sorted Array through Instructions

By zxi on November 8, 2020

Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:

The number of elements currently in nums that are strictly less than instructions[i].
The number of elements currently in nums that are strictly greater than instructions[i].

For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].

Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 10⁹ + 7

Example 1:

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.

Example 2:

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3:

Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

Constraints:

1 <= instructions.length <= 10⁵
1 <= instructions[i] <= 10⁵

Solution: Fenwick Tree / Binary Indexed Tree

Time complexity: O(nlogm)
Space complexity: O(m + n)

m is the maximum value, n is number of values.

C++

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) {

return x & (-x);

}

vector<int> sums_;

};

class Solution {

public:

int createSortedArray(vector<int>& instructions) {

const int n = instructions.size();

FenwickTree tree(1e5);

long ans = 0;

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

int lt = tree.query(instructions[i] - 1);

int gt = i - tree.query(instructions[i]);

ans += min(lt, gt);

tree.update(instructions[i], 1);

}

return ans % 1000000007;

}

};

花花酱 LeetCode 1611. Minimum One Bit Operations to Make Integers Zero

By zxi on October 4, 2020

Given an integer n, you must transform it into 0 using the following operations any number of times:

Change the rightmost (0^th) bit in the binary representation of n.
Change the i^th bit in the binary representation of n if the (i-1)^th bit is set to 1 and the (i-2)^th through 0^th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 0
Output: 0

Example 2:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.

Example 3:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.

Example 4:

Input: n = 9
Output: 14

Example 5:

Input: n = 333
Output: 393

Constraints:

0 <= n <= 10⁹

Solution 1: Graycode

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

Ans is the order of n in graycode.

C++

// Author: Huahua

class Solution {

public:

int minimumOneBitOperations(int n) {

int ans = 0;

while (n) {

ans ^= n;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 1558. Minimum Numbers of Function Calls to Make Target Array

By zxi on August 22, 2020

Your task is to form an integer array nums from an initial array of zeros arr that is the same size as nums.

Return the minimum number of function calls to make nums from arr.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements)  [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.

Example 2:

Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> [2, 2] (1 operation).
Total of operations: 2 + 1 = 3.

Example 3:

Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5](nums).

Example 4:

Input: nums = [3,2,2,4]
Output: 7

Example 5:

Input: nums = [2,4,8,16]
Output: 8

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

Solution: count 1s

For 5 (101b), we can add 1s for 5 times which of cause isn’t the best way to generate 5, the optimal way is to [+1, *2, +1]. We have to add 1 for each 1 in the binary format. e.g. 11 (1011), we need 3x “+1” op, and 4 “*2” op. Fortunately, the “*2” can be shared/delayed, thus we just need to find the largest number.
e.g. [2,4,8,16]
[0, 0, 0, 0] -> [0, 0, 0, 1] -> [0, 0, 0, 2]
[0, 0, 0, 2] -> [0, 0, 1, 2] -> [0, 0, 2, 4]
[0, 0, 2, 4] -> [0, 1, 2, 4] -> [0, 2, 4, 8]
[0, 2, 4, 8] -> [1, 2, 4, 8] -> [2, 4, 8, 16]
ans = sum{count_1(arr_i)} + high_bit(max(arr_i))

Time complexity: O(n*log(max(arr_i))
Space complexity: O(1)

C++

class Solution {

public:

int minOperations(vector<int>& nums) {

int ans = 0;

int high = 0;

for (int x : nums) {

high = max(high, 31 - __builtin_clz(x | 1));

ans += std::bitset<32>(x).count();

}

return ans + high;

}

};

Java

class Solution {

public int minOperations(int[] nums) {

int ans = 0;

int high = 0;

for (int x : nums) {

int l = -1;

while (x != 0) {

ans += x & 1;

x >>= 1;

++l;

}

high = Math.max(high, l);

}

return ans + high;

}

Python3

class Solution:

def minOperations(self, nums: List[int]) -> int:

return sum(bin(x).count('1') for x in nums) + len(bin(max(nums))) - 3

花花酱 LeetCode 1529. Bulb Switcher IV

By zxi on July 26, 2020

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

Choose any bulb (index i) of your current configuration.
Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

1 <= target.length <= 10^5
target[i] == '0' or target[i] == '1'

Solution: XOR

Flip from left to right, since flipping the a bulb won’t affect anything in the left.
We count how many times flipped so far, and that % 2 will be the state for all the bulb to the right.
If the current bulb’s state != target, we have to flip once.

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

C++

class Solution {

public:

int minFlips(string target) {

int ans = 0;

int cur = 0;

for (char c : target) {

if (c - '0' != cur) {

cur ^= 1;

++ans;

}

return ans;

}

};