Problem Statement
Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:
Copy: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.
Function Signature (Java):
int minSteps(int n)
Inputs:
3
Outputs:
3
Intitally, we have a single 'A'.
In step 1, we copy:
A
In step 2, we paste:
AA
In step 3, we paste again:
AAA
TL;DR Code Solution
public int minSteps(int n) {
int[] dp = new int[n+1];
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = i-1; j > 1; j--) {
if (i % j == 0) {
dp[i] = dp[j] + (i/j);
break;
}
}
}
return dp[n];
}
TL;DR Code Solution
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < (int)nums.size() - 2; i++) {
int pin = nums[i];
int left = i + 1;
int right = (int)nums.size() - 1;
while (left < right) {
if (pin + nums[left] + nums[right] == 0) {
int numLeft = nums[left];
int numRight = nums[right];
vector<int> current = {pin, nums[left], nums[right]};
result.push_back(current);
while (left < right && nums[left] == numLeft)
left++;
while (left < right && nums[right] == numRight)
right--;
}
else if (pin + nums[left] + nums[right] < 0) {
left++;
}
else {
right--;
}
}
while (i + 1 < nums.size() && nums[i + 1] == nums[i])
i++;
}
return result;
}
Problem Statement
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
Function Signature (C++):
int threeSumSmaller(vector<int>& nums, int target)
Inputs:
nums = [-2, 0, 1, 3]
target = 2
Outputs:
2
Two triplets with sums less than 2 can be created:
[-2, 0, 1]
[-2, 0, 3]
TL;DR Code Solution
int threeSumSmaller(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int count = 0;
for (int i = 0; i < (int)nums.size() - 1; i++) {
int pin = nums[i];
int right = (int)nums.size() - 1;
int left = i + 1;
while (left < right) {
int sum = pin + nums[left] + nums[right];
if (sum < target) {
count += right - left;
left++;
}
else {
right--;
}
}
}
return count;
}
Problem Statement
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
Function Signature (C++):
vector<vector<int>> fourSum(vector<int>& nums, int target)
Inputs:
nums = [1, 0, -1, 0, -2, 2]
target = 0
Outputs:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
TL;DR Code Solution
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int size = (int)nums.size();
for (int i = 0; i < size - 3; i++) {
int first = nums[i];
for (int j = i + 1; j < size - 2; j++) {
int second = nums[j];
int left = j + 1;
int right = size - 1;
while (left < right) {
int numLeft = nums[left];
int numRight = nums[right];
int sum = first + second + nums[left] + nums[right];
if (sum == target) {
vector<int> current = {first, second, nums[left], nums[right]};
result.push_back(current);
while (left < right && nums[left] == numLeft)
left++;
while (left < right && nums[right] == numRight)
right--;
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
while (j + 1 < size - 2 && nums[j+1] == nums[j])
j++;
}
while (i + 1 < size - 3 && nums[i+1] == nums[i])
i++;
}
return result;
}
Problem Statement
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Function Signature (C++):
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)
Inputs:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Outputs:
2
We can create two different tuples:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
TL;DR Code Solution
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> sums;
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
sums[A[i] + B[j]]++;
}
}
int count = 0;
for (int i = 0; i < C.size(); i++) {
for (int j = 0; j < D.size(); j++) {
if (sums.find(-(C[i] + D[j])) != sums.end()) {
count += sums[-(C[i] + D[j])];
}
}
}
return count;
}
Problem Statement
Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict.
If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.
Function Signature (C++):
string addBoldTag(string s, vector<string>& dict)
Inputs:
s = "abcxyz123"
dict = ["abc","123"]
Outputs:
"<b>abc</b>xyz<b>123</b>"
Inputs:
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Outputs:
"<b>aaabbc</b>c"
TL;DR Code Solution
string addBoldTag(string s, vector<string>& dict) {
vector<bool> isBold(s.length());
for (int i = 0; i < dict.size(); i++) {
int searchIndex = s.find(dict[i], 0);
while (s.find(dict[i], searchIndex) != std::string::npos) {
for (int j = searchIndex; j < searchIndex + dict[i].length(); j++) {
isBold[j] = true;
}
searchIndex = s.find(dict[i], searchIndex + 1);
}
}
int runner = 0;
string result;
while (runner < s.length()) {
if (!isBold[runner]) {
result += s[runner];
runner++;
}
else {
result += "<b>";
while (runner < s.length() && isBold[runner]) {
result += s[runner];
runner++;
}
result += "</b>";
}
}
return result;
}