Posts tagged as “math”

花花酱 LeetCode 1588. Sum of All Odd Length Subarrays

By zxi on September 19, 2020

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

Constraints:

1 <= arr.length <= 100
1 <= arr[i] <= 1000

Solution 0: Brute Force

Enumerate all odd length subarrys: O(n^2), each take O(n) to compute the sum.

Total time complexity: O(n^3)
Space complexity: O(1)

Solution 1: Running Prefix Sum

Reduce the time complexity to O(n^2)

C++

class Solution {

public:

int sumOddLengthSubarrays(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

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

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

s += arr[j];

ans += s * ((j - i + 1) & 1);

}

return ans;

}

};

Solution 2: Math

Count how many times arr[i] can be in of an odd length subarray
we chose the start, which can be 0, 1, 2, … i, i + 1 choices
we chose the end, which can be i, i + 1, … n – 1, n – i choices
Among those 1/2 are odd length.
So there will be upper((i + 1) * (n – i) / 2) odd length subarrays contain arr[i]

ans = sum(((i + 1) * (n – i) + 1) / 2 * arr[i] for in range(n))

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

C++

class Solution {

public:

int sumOddLengthSubarrays(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

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

ans += ((i + 1) * (n - i) + 1) / 2 * arr[i];

return ans;

}

};

花花酱 LeetCode 1573. Number of Ways to Split a String

By zxi on September 5, 2020

Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

Example 2:

Input: s = "1001"
Output: 0

Example 3:

Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"

Example 4:

Input: s = "100100010100110"
Output: 12

Constraints:

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

Solution: Counting

Count how many ones in the binary string as T, if not a factor of 3, then there is no answer.

Count how many positions that have prefix sum of T/3 as l, and how many positions that have prefix sum of T/3*2 as r.

Ans = l * r

But we need to special handle the all zero cases, which equals to C(n-2, 2) = (n – 1) * (n – 2) / 2

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

C++

class Solution {

public:

int numWays(string s) {

const int kMod = 1e9 + 7;

const long n = s.length();

int t = 0;

for (char c : s) t += c == '1';

if (t % 3) return 0;

if (t == 0)

return ((1 + (n - 2)) * (n - 2) / 2) % kMod;

t /= 3;

long l = 0;

long r = 0;

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

c += (s[i] == '1');

if (c == t) ++l;

else if (c == t * 2) ++r;

}

return (l * r) % kMod;

}

};

Python3

class Solution:

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

n = len(s)

t = s.count('1')

if t % 3 != 0: return 0

if t == 0: return ((n - 1) * (n - 2) // 2) % (10**9 + 7)

t //= 3

l, r, c = 0, 0, 0

for i, ch in enumerate(s):

if ch == '1': c += 1

if c == t: l += 1

elif c == t * 2: r += 1

return (l * r) % (10**9 + 7)

One pass: Space complexity: O(n)

Python3

class Solution:

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

n = len(s)

p = defaultdict(int)

c = 0

for ch in s:

if ch == '1': c += 1

p[c] += 1

if c % 3 != 0: return 0

if c == 0: return ((n - 1) * (n - 2) // 2) % (10**9 + 7)

return (p[c // 3] * p[c // 3 * 2]) % (10**9 + 7)

花花酱 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST

By zxi on August 30, 2020

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

Example 2:

Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.

Example 4:

Input: nums = [3,1,2,5,4,6]
Output: 19

Example 5:

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
All integers in nums are distinct.

Solution: Recursion + Combinatorics

For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l / r nodes, we have ways(left) / ways(right) different ways to re-arrange those nodes. So the total # of ways is:
C(l + r, l) * ways(l) * ways(r)
Don’t forget to minus one for the final answer.

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

class Solution {

public:

int numOfWays(vector<int>& nums) {

const int n = nums.size();

const int kMod = 1e9 + 7;

vector<vector<int>> cnk(n + 1, vector<int>(n + 1, 1));

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

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

cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % kMod;

function<int(vector<int>)> trees = [&](const vector<int>& nums) {

const int n = nums.size();

if (n <= 2) return 1;

vector<int> left;

vector<int> right;

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

if (nums[i] < nums[0]) left.push_back(nums[i]);

else right.push_back(nums[i]);

long ans = cnk[n - 1][left.size()];

ans = (ans * trees(left)) % kMod;

ans = (ans * trees(right)) % kMod;

return static_cast<int>(ans);

};

return trees(nums) - 1;

}

};

python3

class Solution:

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

def ways(nums):

if len(nums) <= 2: return 1

l = [x for x in nums if x < nums[0]]

r = [x for x in nums if x > nums[0]]

return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)

return (ways(nums) - 1) % (10**9 + 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 1503. Last Moment Before All Ants Fall Out of a Plank

By zxi on July 5, 2020

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Example 1:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).

Example 2:

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Example 3:

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.

Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6

Constraints:

1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
All values of left and right are unique, and each value can appear only in one of the two arrays.

Solution: Keep Walking

When two ants A –> and <– B meet at some point, they change directions <– A B –>, we can swap the ids of the ants as <– B A–>, so it’s the same as walking individually and passed by. Then we just need to find the max/min of the left/right arrays.

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

C++

// Author: Huahua

class Solution {

public:

int getLastMoment(int n, vector<int>& left, vector<int>& right) {

const int t1 = left.empty() ? 0 : *max_element(cbegin(left), cend(left));

const int t2 = right.empty() ? 0 : n - *min_element(cbegin(right), cend(right));

return max(t1, t2);

}

};

Java

// Author: Huahua

class Solution {

public int getLastMoment(int n, int[] left, int[] right) {

int t1 = left.length == 0 ? 0 : Arrays.stream(left).max().getAsInt();

int t2 = right.length == 0 ? 0 : n - Arrays.stream(right).min().getAsInt();

return Math.max(t1, t2);

}

Python3

# Author: Huahua

class Solution:

def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:

t1 = max(left) if left else 0

t2 = n - min(right) if right else 0

return max(t1, t2)