# Posts tagged as “combination”

Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 109 + 7.

Example 1:

Input: n = 4, k = 2
Output: 5
Explanation:
The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.


Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.


Example 4:

Input: n = 5, k = 3
Output: 7


Example 5:

Input: n = 3, k = 2
Output: 1

Constraints:

• 2 <= n <= 1000
• 1 <= k <= n-1

## Solution 1: Naive DP (TLE)

dp[n][k] := ans of problem(n, k)
dp[n] = n * (n – 1) / 2 # C(n,2)
dp[n][k] = 1 if k == n – 1
dp[n][k] = 0 if k >= n
dp[n][k] = sum((i – 1) * dp(n – i + 1, k – 1) 2 <= i < n

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

## Solution 2: DP w/ Prefix Sum

Time complexity: O(nk)
Space complexity: O(nk)

## Solution 3: DP / 3D State

Time complexity: O(nk)
Space complexity: O(nk)

## Solution 4: DP / Mathematical induction

Time complexity: O(nk)
Space complexity: O(nk)

## Solution 5: DP / Reduction

This problem can be reduced to: given n + k – 1 points, pick k segments (2*k points).
if two consecutive points were selected by two segments e.g. i for A and i+1 for B, then they share a point in the original space.
Answer C(n + k – 1, 2*k)

Time complexity: O((n+k)*2) Pascal’s triangle
Space complexity: O((n+k)*2)

## C++

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [fromi, toi] represents an employee’s request to transfer from building fromi to building toi.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Example 1:

Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explantion: Let's see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don't have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.


Example 2:

Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3
Explantion: Let's see the requests:
From building 0 we have employee x and they want to stay in the same building 0.
From building 1 we have employee y and they want to move to building 2.
From building 2 we have employee z and they want to move to building 1.
We can achieve all the requests. 

Example 3:

Input: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output: 4


Constraints:

• 1 <= n <= 20
• 1 <= requests.length <= 16
• requests[i].length == 2
• 0 <= fromi, toi < n

## Solution: Combination

Try all combinations: O(2^n * (r + n))
Space complexity: O(n)

## Python3

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.


Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].


Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.


Constraints:

• 1 <= s.length <= 16
• s contains only lower case English letters.

## Solution: Brute Force

Try all combinations.
Time complexity: O(2^n)
Space complexity: O(n)

## DFS/C++

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

• Type 1: Triplet (i, j, k) if nums1[i]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
• Type 2: Triplet (i, j, k) if nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1^2 = nums2 * nums2. (4^2 = 2 * 8).


Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].


Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1^2 = nums2 * nums2.
Type 2: (3,0,1).  nums2^2 = nums1 * nums1.


Example 4:

Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.


Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 1 <= nums1[i], nums2[i] <= 10^5

## Solution: Hashtable

For each number y in the second array, count its frequency.

For each number x in the first, if x * x % y == 0, let r = x * x / y
if r == y: ans += f[y] * f[y-1]
else ans += f[y] * f[r]

Final ans /= 2

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

## C++

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)

## Python3

One pass: Space complexity: O(n)

## Python3

Mission News Theme by Compete Themes.