Find how many integers i (1 ≤ i ≤ 12) satisfy that the length of S[i] is i
Techniques: Iteration
Index | String | Size | Answer |
1 | january | 7 | 0 |
2 | february | 8 | 0 |
3 | may | 3 | 1 |
By: Win Chang
By: Win Chang
Find the total distance traveled to type out A~Z in order given the keyboard.
Techniques: Iteration
Keyboard A~F:
B | D | C | A | F | E |
3
2
1
4
1
By: Win Chang
By: Win Chang
Find max(A) + max(B)
Techniques: Iteration / function usage
C++ Built-in Function: *max_element(x.begin(), x.end())
By: Win Chang
By: Win Chang
Given a directed graph of N nodes and M edges, edge i connects node u to node v with weight w. Assign each node a value, satisfying the following condition:
X[v] - X[u] = W[i] holds, where X stores the value for each node.
By: Win Chang
By: Win Chang
Techniques: DFS
X[2] - X[1] = 3
X[1] - X[2] = -3
Starting from node 1 and let X[1] = 0, perform DFS.
Set X[v] = W[i] + X[u] if node v has not yet been visited.
1
2
3
-3
By: Win Chang
By: Win Chang
Given an array A of length N where A[i] denotes the votes i-th candidate initially received. A candidate will win the election if and only if the number of candidates, whose votes are greater than this candidate’s, is less than M. There are a total of K votes in the election, meaning there are (K - 𝚺A) votes left.
For each of the candidates:
By: Win Chang
By: Win Chang
N = 5, M = 2, K = 16
A: {3, 1, 4, 1, 5}
For the first candidate, receiving one more vote will win since there will only be one candidate with votes greater than them.
In the worst case scenario, the remaining one vote will go to the 3rd candidate, becoming a total of two candidates with votes greater than first candidate. Hence, two votes must be received by first candidate in order to guarantee the win.
By: Win Chang
By: Win Chang
For i-th candidate, binary search the answer (0 ≤ answer ≤ K - 𝜮A), let’s denote the current testing number X:
Let’s denote the index of the first number greater than A[i] + X by u.
Techniques: Binary Search + Prefix Sum
In sorted A (ascending order), there exists an index j (0 ≤ j ≤ u) where all the candidates in between j and u (inclusive) will exceed i-th candidate’s # of votes by possibly receiving some more votes from those remaining.
By: Win Chang
By: Win Chang
If (A.size() - j) < M, the i-th candidate will always win (make sure you exclude i-th candidate in the process of searching for j to prevent getting WA if the index of the value of i-th candidate in sorted A is greater than or equal to j), therefore X is a valid answer.
You’ll need to binary search the index j, and use prefix sum to optimize the time complexity.
By: Win Chang
By: Win Chang
N = 5, M = 2, K = 16
A: {3, 1, 4, 1, 5}
V: {1, 1, 3, 4, 5}
For 1st candidate, at index 0:
X = 1:
u = 4 (the index of the first number greater than A[0] + 1 = 4)
j = 3 (3rd and 5th candidates will exceed 1st candidate’s vote since 3rd might receive the remain one vote, so both of them have 5 votes)
(A.size() - j) < m? 5 - 3 < 1?
X = 2
By: Win Chang
By: Win Chang
Sample Codes:
By: Win Chang
By: Win Chang