Huahua's Tech Road

花花酱 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 1557. Minimum Number of Vertices to Reach All Nodes

By zxi on August 22, 2020

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i] represents a directed edge from node from_i to node to_i.

Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Example 2:

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]
Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

Constraints:

2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= from_i, to_i < n
All pairs (from_i, to_i) are distinct.

Solution: In degree

Nodes with 0 in degree will be the answer.
Time complexity: O(E+V)
Space complexity: O(V)

C++

class Solution {

public:

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {

vector<int> in(n);

for (const auto& e : edges) ++in[e[1]];

vector<int> ans;

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

if (in[i] == 0) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 1556. Thousand Separator

By zxi on August 22, 2020

Given an integer n, add a dot (“.”) as the thousands separator and return it in string format.

Example 1:

Input: n = 987
Output: "987"

Example 2:

Input: n = 1234
Output: "1.234"

Example 3:

Input: n = 123456789
Output: "123.456.789"

Example 4:

Input: n = 0
Output: "0"

Constraints:

0 <= n < 2^31

Solution: Digit by digit

Time complexity: O(log^2(n)) -> O(logn)
Space complexity: O(log(n))

C++

class Solution {

public:

string thousandSeparator(int n) {

string ans;

int count = 0;

do {

if (count++ % 3 == 0 && ans.size())

ans = "." + ans;

ans = to_string(n % 10) + ans;

n /= 10;

} while (n);

return ans;

}

};

花花酱 LeetCode 1553. Minimum Number of Days to Eat N Oranges

By zxi on August 16, 2020

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat 2*(n/3) oranges.

You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 56
Output: 6

Constraints:

1 <= n <= 2*10^9

Solution: Greedy + DP

Eat oranges one by one to make it a multiply of 2 or 3 such that we can eat 50% or 66.66…% of the oranges in one step.
dp(n) := min steps to finish n oranges.
base case n <= 1, dp(n) = n
transition: dp(n) = 1 + min(n%2 + dp(n/2), n % 3 + dp(n / 3))
e.g. n = 11,
we eat 11%2 = 1 in one step, left = 10 and then eat 10 / 2 = 5 in another step. 5 left for the subproblem.
we eat 11%3 = 2 in two steps, left = 9 and then eat 9 * 2 / 3 = 6 in another step, 3 left for the subproblem.
dp(11) = 1 + min(1 + dp(5), 2 + dp(3))

T(n) = 2*T(n/2) + O(1) = O(n)
Time complexity: O(n) // w/o memoization, close to O(logn) in practice.
Space complexity: O(logn)

C++

class Solution {

public:

int minDays(int n) {

unordered_map<int, int> cache;

function<int(int)> dp = [&](int n) {

if (n <= 1) return n;

auto it = cache.find(n);

if (it != cache.end()) return it->second;

return cache[n] = 1 + min(n % 2 + dp(n / 2), n % 3 + dp(n / 3));

};

return dp(n);

}

};

Java

class Solution {

private static Map<Integer, Integer> cache = new HashMap<>();

public int minDays(int n) {

return dp(n);

}

private int dp(int n) {

if (n <= 1) return n;

if (cache.containsKey(n)) return cache.get(n);

int ans = 1 + Math.min(n % 2 + dp(n / 2), n % 3 + dp(n / 3));

cache.put(n, ans);

return ans;

}

Python3

class Solution:

def minDays(self, n: int) -> int:

@lru_cache(None)

def dp(n):

if n <= 1: return n

return 1 + min(n % 2 + dp(n // 2), n % 3 + dp(n // 3))

return dp(n)

Solution 2: BFS

if x % 2 == 0, push x/2 onto the queue
if x % 3 == 0, push x/3 onto the queue
always push x – 1 onto the queue

C++

class Solution {

public:

int minDays(int n) {

queue<int> q{{n}};

unordered_set<int> seen;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int x = q.front(); q.pop();

if (x == 0) return steps;

if (x % 2 == 0 && seen.insert(x / 2).second)

q.push(x / 2);

if (x % 3 == 0 && seen.insert(x / 3).second)

q.push(x / 3);

if (seen.insert(x - 1).second)

q.push(x - 1);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1552. Magnetic Force Between Two Balls

By zxi on August 15, 2020

In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the i^th basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Constraints:

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
All integers in position are distinct.
2 <= m <= position.length

Solution: Binary Search

Find the max distance that we can put m balls.

Time complexity: O(n*log(distance))
Space complexity: O(1)

C++

class Solution {

public:

int maxDistance(vector<int>& position, int m) {

const int n = position.size();

sort(begin(position), end(position));

auto count = [&](int d) -> int {

int last = position[0];

int ans = 1;

for (int x : position) {

if (x - last >= d) {

last = x;

++ans;

}

return ans;

};

int l = 0;

int t = (position.back() - position.front()) + 1;

int r = t;

while (l < r) {

int mid = l + (r - l) / 2;

if (count(t - mid) >= m) // find min of l => max of t - l

r = mid;

else

l = mid + 1;

}

return t - l;

}

};

Java

class Solution {

public int maxDistance(int[] position, int m) {

Arrays.sort(position);

final int n = position.length;

int l = 0;

int r = position[n - 1] - position[0] + 1;

int t = r;

while (l < r) {

int mid = l + (r - l) / 2;

if (getCount(position, t - mid) >= m)

r = mid;

else

l = mid + 1;

}

return t - l;

}

private int getCount(int[] position, int d) {

int count = 1;

int last = position[0];

for (int x : position) {

if (x - last >= d) {

++count;

last = x;

}

return count;

}

Python3

class Solution:

def maxDistance(self, position: List[int], m: int) -> int:

position.sort()

def getCount(d: int) -> int:

last, count = position[0], 1

for x in position:

if x - last >= d:

last = x

count += 1

return count

l, r = 0, position[-1] - position[0] + 1

t = r

while l < r:

mid = l + (r - l) // 2

if getCount(t - mid) >= m:

r = mid

else:

l = mid + 1

return t - l