# Posts tagged as “hard”

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1


Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1


Example 3:

Input: nums = [3,6]
Output: false


Constraints:

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

## Solution: Math

Bézout’s lemma: b * A + b * A + …. + b[n] * A[n] = 1 <==> gcd(A, A, …, A[n]) = 1 <=> at least two numbers are co-prime

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

## C++

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5


Example 3:

Input: n = 11, m = 13
Output: 6

## Solution1: DP + Cheating

DP can not handle case 3, for m, n <= 13, (11,13) is the only case of that special case.

dp[i][j] := min squares to tile a i x j rectangle.

dp[i][i] = 1

dp[i][j] = min(dp[r][j] + dp[i-r][j], dp[i][c] + dp[i][j – c]), 1 <= r <= i/2, 1 <= c <= j /2

Time complexity: O(m*n*max(n, m))
Space complexity: O(m*n)

## C++

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job.
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.


Example 2:


Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.


Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6


Constraints:

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

## Solution: DP + binary search

Sort jobs by ending time.
dp[t] := max profit by end time t.

for a job = (s, e, p)
dp[e] = dp[u] + p, u <= s, and if dp[u] + p > last_element in dp.

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

## C++

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

• Each character is a lower case vowel ('a''e''i''o''u')
• Each vowel 'a' may only be followed by an 'e'.
• Each vowel 'e' may only be followed by an 'a' or an 'i'.
• Each vowel 'i' may not be followed by another 'i'.
• Each vowel 'o' may only be followed by an 'i' or a 'u'.
• Each vowel 'u' may only be followed by an 'a'.

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

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".


Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".


Example 3:

Input: n = 5
Output: 68

Constraints:

• 1 <= n <= 2 * 10^4

## Solution: DP

dp[i][c] := number of strings of length i ends with letter c
ans = sum(dp[n])

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

## Solution 2: Matrix multiplication

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

## C++

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]

## Solution: DFS

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

## Related Problems

Mission News Theme by Compete Themes.