Huahua’s Tech Road

花花酱 LeetCode 1526. Minimum Number of Increments on Subarrays to Form a Target Array

By zxi on July 25, 2020

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).

Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).

Example 4:

Input: target = [1,1,1,1]
Output: 1

Constraints:

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

Solution:

If arr[i] < arr[i – 1], if we can generate arr[i] then we can always generate arr[i] with no extra cost.
e.g. [3, 2, 1] 3 < 2 < 1, [0,0,0] => [1,1,1] => [2, 2, 1] => [3, 2, 1]

So we only need to handle the case of arr[i] > arr[i – 1], we can reuse the computation, with extra cost of arr[i] – arr[i-1].
e.g. [2, 5]: [0,0] => [1, 1] => [2, 2], it takes 2 steps to cover arr[0].
[2,2] => [2, 3] => [2, 4] => [2, 5], takes another 3 steps (arr[1] – arr[0] / 5 – 2) to cover arr[1].

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

C++

class Solution {

public:

int minNumberOperations(vector<int>& target) {

int ans = target[0];

for (int i = 1; i < target.size(); ++i)

ans += max(0, target[i] - target[i - 1]);

return ans;

}

};

花花酱 LeetCode 1525. Number of Good Ways to Split a String

By zxi on July 25, 2020

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.

Return the number of good splits you can make in s.

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2

Constraints:

s contains only lowercase English letters.
1 <= s.length <= 10^5

Solution: Sliding Window

Count the frequency of each letter and count number of unique letters for the entire string as right part.
Iterate over the string, add current letter to the left part, and remove it from the right part.
We only
1. increase the number of unique letters when its frequency becomes to 1
2. decrease the number of unique letters when its frequency becomes to 0

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

C++

class Solution {

public:

int numSplits(string s) {

vector<int> r(26);

vector<int> l(26);

int cr = 0;

for (char c : s)

cr += (++r[c - 'a'] == 1);

int ans = 0;

int cl = 0;

for (char c : s) {

cl += (++l[c - 'a'] == 1);

cr -= (--r[c - 'a'] == 0);

ans += cl == cr;

}

return ans;

}

};

java

class Solution {

public int numSplits(String s) {

int[] l = new int[26];

int[] r = new int[26];

int ans = 0;

int cl = 0;

int cr = 0;

for (char c : s.toCharArray())

if (++r[c - 'a'] == 1) ++cr;

for (char c : s.toCharArray()) {

if (++l[c - 'a'] == 1) ++cl;

if (--r[c - 'a'] == 0) --cr;

if (cl == cr) ++ans;

}

return ans;

}

Python3

class Solution:

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

s = [ord(c) - ord('a') for c in s]

l, r = [0] * 26, [0] * 26

cl, cr, ans = 0, 0, 0

for c in s:

r[c] += 1

if r[c] == 1: cr += 1

for c in s:

l[c] += 1

r[c] -= 1

if l[c] == 1: cl += 1

if r[c] == 0: cr -= 1

if cl == cr: ans += 1

return ans

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

By zxi on July 25, 2020

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Example 4:

Input: arr = [100,100,99,99]
Output: 4

Example 5:

Input: arr = [7]
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 100

Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i][0] := # end with arr[i] has even sum
dp[i][1] := # end with arr[i] has even sum

if arr[i] is even:

dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]

else:

dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1

ans = sum(dp[i][1])

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

C++

class Solution {

public:

int numOfSubarrays(vector<int>& arr) {

const int n = arr.size();

constexpr int kMod = 1e9 + 7;

// dp[i][0] # of subarrays ends with a[i-1] have even sums.

// dp[i][1] # of subarrays ends with a[i-1] have odd sums.

vector<vector<int>> dp(n + 1, vector<int>(2));

long ans = 0;

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

if (arr[i - 1] & 1) {

dp[i][0] = dp[i - 1][1];

dp[i][1] = dp[i - 1][0] + 1;

} else {

dp[i][0] = dp[i - 1][0] + 1;

dp[i][1] = dp[i - 1][1];

}

ans += dp[i][1];

}

return ans % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int numOfSubarrays(int[] arr) {

long ans = 0, odd = 0, even = 0;

for (int x : arr) {

even += 1;

if (x % 2 == 1) {

long t = even; even = odd; odd = t;

}

ans += odd;

}

return (int)(ans % (int)(1e9 + 7));

}

Python3

# Author: Huahua

class Solution:

def numOfSubarrays(self, arr: List[int]) -> int:

ans, odd, even = 0, 0, 0

for x in arr:

if x & 1:

odd, even = even + 1, odd

else:

odd, even = odd, even + 1

ans += odd

return ans % int(1e9 + 7)

花花酱 LeetCode 1523. Count Odd Numbers in an Interval Range

By zxi on July 25, 2020

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

Constraints:

0 <= low <= high <= 10^9

Solution: Math

The count of odd numbers between [1, low – 1] is low / 2
e.g. low = 6, we have [1,3,5] in range [1, 5] and count is 6/2 = 3.
The count of odd numbers between [1, high] is (high + 1) / 2
e.g. high = 7, we have [1,3,5,7] in range [1, 7] and count is (7+1) / 2 = 4

Then the count of odd numbers in range [low, high] = count(1, high) – count(1, low-1)
e.g. in range [6, 7] we only have [7], count: 4 – 3 = 1

ans = (high + 1) / 2 – low / 2

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

C++

// Author: Huahua

class Solution {

public:

int countOdds(int low, int high) {

return (high + 1) / 2 - low / 2;

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 1526. Minimum Number of Increments on Subarrays to Form a Target Array

Solution:

C++

花花酱 LeetCode 1525. Number of Good Ways to Split a String

Solution: Sliding Window

C++

java

Python3

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

Solution: DP

C++

Java

Python3

花花酱 LeetCode 1523. Count Odd Numbers in an Interval Range

Solution: Math

C++

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

Solution: Brute Force w/ Optimization

C++