1. Gymnastic Team Formation
Given the small input constraints, a brute-force approach with backtracking and pruning is suitable. The solution uses depth-first search (DFS) to explore valid permutations while eliminating invalid paths early.
#include <iostream>
using namespace std;
int constraints[11] = {0};
bool used[11] = {false};
int validPermutations = 0;
int teamSize;
void dfs(int position) {
if (position > teamSize) {
validPermutations++;
return;
}
for (int candidate = 1; candidate <= teamSize; ++candidate) {
if (used[candidate]) continue;
if (used[constraints[candidate]]) continue;
used[candidate] = true;
dfs(position + 1);
used[candidate] = false;
}
}
int main() {
cin >> teamSize;
for (int i = 1; i <= teamSize; ++i)
cin >> constraints[i];
dfs(1);
cout << validPermutations << endl;
return 0;
}
2. Maximum Path Sum in Binary Tree
This problem can be solved using a depth-first search approach combined with dynamic programming. The key insight is to compute the maximum path sum through each node by considering left and right subtrees.
class Solution {
private:
int maxSum = INT_MIN;
int calculatePath(TreeNode* node) {
if (!node) return 0;
int left = max(0, calculatePath(node->left));
int right = max(0, calculatePath(node->right));
maxSum = max(maxSum, left + right + node->val);
return node->val + max(left, right);
}
public:
int maxPathSum(TreeNode* root) {
calculatePath(root);
return maxSum;
}
};
3. Longest Increasing Subsequence
Two approaches exist for this problem: dynamic programming with O(N²) complexity, which may time out for larger inputs, and a more efficient greedy approach combined with binary search operating in O(N log N) time.
class Solution {
public:
int findLongestIncreasingSubsequence(vector<int>& nums) {
vector<int> tails;
for (int num : nums) {
if (tails.empty() || num > tails.back()) {
tails.push_back(num);
} else {
int left = 0, right = tails.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] >= num) {
right = mid;
} else {
left = mid + 1;
}
}
tails[left] = num;
}
}
return tails.size();
}
};
4. Prime Product Check
Directly checking if a*b is prime is infeasible for large values. Instead, analyze the problem mathematically: the product is prime only if one factor is 1 and the other is prime.
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(long long x) {
if (x <= 1) return false;
for (long long i = 2; i <= sqrt(x); ++i) {
if (x % i == 0) return false;
}
return true;
}
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
long long a, b;
cin >> a >> b;
if (a == 1 && b == 1) {
cout << "NO" << endl;
} else if (a > 1 && b > 1) {
cout << "NO" << endl;
} else if ((a == 1 && isPrime(b)) || (b == 1 && isPrime(a))) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
5. Longest Common Subsequence
This classic dynamic programming problem compares two strings to find the longest common subsequence by building a table of optimal substructure solutions.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
string s1, s2;
cin >> s1 >> s2;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[n][m] << endl;
return 0;
}
6. Spring Outing Cost Optimization
Use greedy strategy with case analysis to minimize costs for boat rentals based on per-person cost comparisons between different boat types.
#include <iostream>
using namespace std;
long long calculateMinCost(long long people, long long singleCost, long long tripleCost) {
if (people <= 2) return min(singleCost, tripleCost);
long long total = 0;
int remainder = people % 2;
if (3 * singleCost <= 2 * tripleCost) {
total += singleCost * (people / 2);
if (remainder == 1)
total += min(singleCost, min(tripleCost, tripleCost - singleCost));
} else {
total += tripleCost * (people / 3);
remainder = people % 3;
if (remainder == 1)
total += min(singleCost, min(tripleCost, 2 * singleCost - tripleCost));
else if (remainder == 2)
total += min(singleCost, min(tripleCost, 3 * singleCost - tripleCost));
}
return total;
}
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
long long n, a, b;
cin >> n >> a >> b;
cout << calculateMinCost(n, a, b) << endl;
}
return 0;
}
7. Activity Scheduling
Solve interval scheduling problems by sorting intervals and greedily selecting non-overlapping activities with earliest finish times.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> intervals(n);
for (int i = 0; i < n; ++i) {
int start, end;
cin >> start >> end;
intervals[i] = {start, end};
}
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
return a.first < b.first;
});
vector<pair<int, int>> selected;
selected.push_back(intervals[0]);
for (int i = 1; i < n; ++i) {
auto [curStart, curEnd] = intervals[i];
auto [lastStart, lastEnd] = selected.back();
if (curStart < lastEnd) {
if (curEnd < lastEnd) {
selected.pop_back();
selected.push_back({curStart, curEnd});
}
} else {
selected.push_back({curStart, curEnd});
}
}
cout << selected.size() << endl;
return 0;
}
8. Choir Formation
Dynamic programming solution using two tables to track maximum and minimum products when selecting k members with minimum distance constraints between positions.
#include <iostream>
#include <vector>
using namespace std;
const long long NEG_INF = -1e18;
const long long POS_INF = 1e18;
int main() {
int n;
cin >> n;
vector<long long> arr(n + 1);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
int k, d;
cin >> k >> d;
vector<vector<long long>> maxProduct(n + 1, vector<long long>(k + 1, NEG_INF));
vector<vector<long long>> minProduct(n + 1, vector<long long>(k + 1, POS_INF));
for (int i = 1; i <= n; ++i) {
maxProduct[i][1] = minProduct[i][1] = arr[i];
for (int j = 2; j <= min(i, k); ++j) {
for (int prev = i - 1; prev >= max(i - d, j - 1); --prev) {
maxProduct[i][j] = max({maxProduct[prev][j - 1] * arr[i], minProduct[prev][j - 1] * arr[i], maxProduct[i][j]});
minProduct[i][j] = min({minProduct[prev][j - 1] * arr[i], maxProduct[prev][j - 1] * arr[i], minProduct[i][j]});
}
}
}
long long result = NEG_INF;
for (int i = k; i <= n; ++i)
result = max(result, maxProduct[i][k]);
cout << result << endl;
return 0;
}
9. Extended Jumping Stairs
Optimize the problem of counting ways to climb stairs by recognizing the pattern of powers of two, reducing time complexity from O(N²) to O(N).
#include <iostream>
using namespace std;
int main() {
int steps;
cin >> steps;
long long result = 1;
for (int i = 1; i < steps; ++i)
result *= 2;
cout << result << endl;
return 0;
}
10. String Permutations
Generate all unique permutations of a string using DFS with pruning to handle duplicate characters efficiently.
class Solution {
vector<string> results;
string current;
string input;
bool used[11];
int length;
void generate(int pos) {
if (pos == length) {
results.push_back(current);
return;
}
for (int i = 0; i < length; ++i) {
if (used[i]) continue;
if (i > 0 && input[i] == input[i - 1] && !used[i - 1]) continue;
used[i] = true;
current += input[i];
generate(pos + 1);
current.pop_back();
used[i] = false;
}
}
public:
vector<string> generatePermutations(string str) {
length = str.size();
input = str;
sort(input.begin(), input.end());
memset(used, false, sizeof(used));
generate(0);
return results;
}
};
11. Longest Increasing Path in Matrix
Use memoization to optimize DFS for finding the longest increasing path in a matrix, storing results of subproblems to avoid redundant calculations.
class Solution {
int rows, cols;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int memo[1010][1010];
int dfs(vector<vector<int>>& matrix, int i, int j) {
if (memo[i][j] != -1) return memo[i][j];
int length = 1;
for (int k = 0; k < 4; ++k) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] > matrix[i][j]) {
length = max(length, 1 + dfs(matrix, x, y));
}
}
memo[i][j] = length;
return length;
}
public:
int findLongestPath(vector<vector<int>>& matrix) {
rows = matrix.size();
cols = matrix[0].size();
memset(memo, -1, sizeof(memo));
int result = 1;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j)
result = max(result, dfs(matrix, i, j));
return result;
}
};
12. Edit Distance Calculation
Dynamic programming solution for computing the minimum number of operations required to convert one string into another using insert, delete, or replace operations.
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
int n = s1.size(), m = s2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i) dp[i][0] = i;
for (int j = 1; j <= m; ++j) dp[0][j] = j;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
}
cout << dp[n][m] << endl;
}
return 0;
}
13. Huffman Coding Implementation
Construct Huffman tree using a min-heap to compute the minimum total length of encoded data based on character frequencies.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<long long, vector<long long>, greater<long long>> heap;
for (int i = 0; i < n; ++i) {
long long freq;
cin >> freq;
heap.push(freq);
}
long long total = 0;
while (heap.size() > 1) {
long long a = heap.top(); heap.pop();
long long b = heap.top(); heap.pop();
total += a + b;
heap.push(a + b);
}
cout << total << endl;
return 0;
}
14. Counting Subsequences with Pattern "abb"
Dynamic programming with hash tables to efficiently count occurrences of specific patterns in a string using linear time complexity.
#include <iostream>
using namespace std;
const int MAX = 1e5 + 10;
long long patternCount[26] = {0};
long long charCount[26] = {0};
int main() {
int n;
string s;
cin >> n >> s;
long long result = 0;
for (int i = 0; i < n; ++i) {
int index = s[i] - 'a';
result += patternCount[index];
patternCount[index] += i - charCount[index];
charCount[index]++;
}
cout << result << endl;
return 0;
}
15. Second Maximum in Prefix Array
Preprocess the array to store maximum and second maximum values for all prefixes, enabling constant-time queries for each prefix.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n + 1), maxVal(n + 1), secondMax(n + 1);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
for (int i = 1; i <= n; ++i) {
maxVal[i] = max(maxVal[i - 1], arr[i]);
if (arr[i] > secondMax[i - 1] && arr[i] < maxVal[i - 1])
secondMax[i] = arr[i];
else if (arr[i] >= maxVal[i - 1])
secondMax[i] = maxVal[i - 1];
else
secondMax[i] = secondMax[i - 1];
}
int queries;
cin >> queries;
while (queries--) {
int x;
cin >> x;
cout << secondMax[x] << endl;
}
return 0;
}
16. Maximum Sum Divisible by K
Solve the subset sum problem with divisibility constraints using dynamic programming and modular arithmetic properties.
#include <iostream>
#include <cstring>
using namespace std;
const long long NEG_INF = -1e18;
int main() {
int n, k;
cin >> n >> k;
vector<long long> arr(n + 1);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
vector<vector<long long>> dp(n + 1, vector<long long>(k, NEG_INF));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < k; ++j) {
dp[i][j] = dp[i - 1][j];
int prev = (j - (arr[i] % k) + k) % k;
dp[i][j] = max(dp[i][j], dp[i - 1][prev] + arr[i]);
}
}
if (dp[n][0] <= 0) cout << -1 << endl;
else cout << dp[n][0] << endl;
return 0;
}
17. Minimum Perfect Squares Sum
Dynamic programming solution for the coin change problem variant where coins are perfect squares, optimized with space reduction.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int target;
cin >> target;
vector<int> dp(target + 1, 1e9);
dp[0] = 0;
for (int i = 1; i * i <= target; ++i) {
for (int j = i * i; j <= target; ++j) {
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
cout << dp[target] << endl;
return 0;
}
18. Minimum Character Adjustments
Calculate the minimum operations needed to transform all characters in a string to the same letter using circular alphabet adjustments.
#include <iostream>
#include <climits>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
int minOps = INT_MAX;
for (int i = 0; i < 26; ++i) {
char target = 'a' + i;
int ops = 0;
for (char c : s) {
int diff = abs(c - target);
ops += min(diff, 26 - diff);
}
minOps = min(minOps, ops);
}
cout << minOps << endl;
return 0;
}
19. Mountain Array Formation
Combine longest increasing and decreasing subsequences to find the minimum removals needed to form a mountain array structure.
#include <iostream>
using namespace std;
const int MAX = 1010;
int arr[MAX], inc[MAX], dec[MAX];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> arr[i];
for (int i = 1; i <= n; ++i) {
inc[i] = 1;
for (int j = 1; j < i; ++j)
if (arr[j] < arr[i]) inc[i] = max(inc[i], inc[j] + 1);
}
for (int i = n; i > 0; --i) {
dec[i] = 1;
for (int j = i + 1; j <= n; ++j)
if (arr[i] > arr[j]) dec[i] = max(dec[i], dec[j] + 1);
}
int maxLen = 0;
for (int i = 1; i <= n; ++i)
maxLen = max(maxLen, inc[i] + dec[i] - 1);
cout << n - maxLen << endl;
return 0;
}
20. Dark Monster Consumption
Linear dynamic programming solution for maximizing energy consumption with constraints on consecutive selections.
#include <iostream>
using namespace std;
const int MAX = 1e5 + 10;
long long arr[MAX], dp[MAX];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> arr[i];
for (int i = 3; i <= n; ++i)
dp[i] = max(dp[i - 3] + arr[i - 1], dp[i - 1]);
cout << dp[n] << endl;
return 0;
}
21. Bridge Crossing with Floating Blocks
Breadth-first search approach to find the minimum jumps needed to cross a river with floating blocks using greedy interval expansion.
#include <iostream>
using namespace std;
int n;
const int MAX = 2010;
int blocks[MAX];
int findJumps() {
int jumps = 0;
int left = 1, right = 1;
while (left <= right) {
int maxReach = right;
jumps++;
for (int i = left; i <= right; ++i)
maxReach = max(maxReach, i + blocks[i]);
if (maxReach >= n) return jumps;
left = right + 1;
right = maxReach;
}
return -1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> blocks[i];
cout << findJumps() << endl;
return 0;
}
22. Maximum Difference in Array
Single-pass greedy algorithm to find the maximum difference between two elements where the smaller element comes before the larger one.
int calculateMaxDifference(vector<int>& nums) {
int maxDiff = 0;
int minSoFar = nums[0];
for (int num : nums) {
minSoFar = min(minSoFar, num);
maxDiff = max(maxDiff, num - minSoFar);
}
return maxDiff;
}
23. Coin Change Problem
Dynamic programming solution for the classic coin change problem using space-optimized tabulation for minimum coin count.
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 1e9;
int main() {
int n, target;
cin >> n >> target;
vector<int> coins(n);
for (int i = 0; i < n; ++i) cin >> coins[i];
vector<int> dp(target + 1, INF);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= target; ++j)
dp[j] = min(dp[j], dp[j - coin] + 1);
}
cout << (dp[target] == INF ? -1 : dp[target]) << endl;
return 0;
}
24. Substring Count with Unique Characters
Sliding window technique with prefix sums to count substrings with unique character counts within specified ranges efficient.
#include <iostream>
using namespace std;
long long countSubstrings(string& s, int maxUnique) {
if (maxUnique == 0) return 0;
int left = 0, right = 0, unique = 0;
long long count = 0;
int freq[26] = {0};
while (right < s.size()) {
if (freq[s[right] - 'a']++ == 0) unique++;
while (unique > maxUnique) {
if (--freq[s[left] - 'a'] == 0) unique--;
left++;
}
count += right - left + 1;
right++;
}
return count;
}
int main() {
int n, l, r;
string s;
cin >> n >> l >> r >> s;
cout << countSubstrings(s, r) - countSubstrings(s, l - 1) << endl;
return 0;
}
25. Probability of Card Draw
Calculate combinatorial probability for drawing specific cards using iterative multiplication and division of fractions.
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
double prob = 1.0;
for (int i = n; i > n - m; --i) prob *= i;
for (int i = m; i > 1; --i) prob /= i;
prob *= pow(0.8, m) * pow(0.2, n - m);
cout << fixed << setprecision(4) << prob << endl;
return 0;
}
26. Pair Counting with Range Constraints
Sort the array and use sliding window technique to count pairs within specified distance ranges efficiently.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long countPairs(vector<int>& nums, int maxDiff) {
int left = 0, right = 0;
long long count = 0;
while (right < nums.size()) {
while (nums[right] - nums[left] > maxDiff) left++;
count += right - left;
right++;
}
return count;
}
int main() {
int n, l, r;
cin >> n >> l >> r;
vector<int> nums(n);
for (int i = 0; i < n; ++i) cin >> nums[i];
sort(nums.begin(), nums.end());
cout << countPairs(nums, r) - countPairs(nums, l - 1) << endl;
return 0;
}
27. Cyclic Tower of Hanoi
Dynamic programming solution for the cyclic Tower of Henoi problem where moves are restricted to clockwise directions only.
#include <iostream>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
int n;
cin >> n;
long long a = 1, b = 2;
for (int i = 1; i < n; ++i) {
long long x = a, y = b;
a = (2 * y + 1) % MOD;
b = (2 * y + x + 2) % MOD;
}
cout << a << " " << b << endl;
return 0;
}
28. Prime Factor Selection
Depth-first search with pruning to select distinct prime factors from multiple numbers to minimize their sum.
#include <iostream>
#include <cmath>
using namespace std;
const int MAX = 15;
int n, arr[MAX], path = 0, result = INT_MAX;
bool used[1010];
bool isPrime(int x) {
if (x <= 1) return false;
for (int i = 2; i <= sqrt(x); ++i)
if (x % i == 0) return false;
return true;
}
void dfs(int pos) {
if (pos == n) {
result = min(result, path);
return;
}
for (int i = 2; i <= arr[pos]; ++i) {
if (arr[pos] % i != 0 || used[i] || !isPrime(i)) continue;
used[i] = true;
path += i;
dfs(pos + 1);
used[i] = false;
path -= i;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> arr[i];
dfs(0);
cout << (result == INT_MAX ? -1 : result) << endl;
return 0;
}
29. Minimum Changes for Non-decreasing Sequence
Use binary search to find the longest non-decreasing subsequence and subtract from total length to get minimum changes required.
#include <iostream>
using namespace std;
const int MAX = 1e6 + 10;
char dp[MAX];
string s;
int main() {
int n;
cin >> n >> s;
int len = 0;
for (int i = 0; i < n; ++i) {
if (len == 0 || s[i] >= dp[len])
dp[++len] = s[i];
else {
int left = 0, right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[mid] <= s[i]) left = mid + 1;
else right = mid;
}
dp[left] = s[i];
}
}
cout << n - len << endl;
return 0;
}
30. Counting Shortest Paths in Grid
Breadth-first search with path counting to determine the number of shortest paths from multiple sources to a target in a grid.
int countShortestPaths(vector<vector<int>>& grid, int rows, int cols) {
vector<vector<int>> dist(rows, vector<int>(cols, -1));
vector<vector<int>> paths(rows, vector<int>(cols, 0));
queue<pair<int, int>> q;
int targetX, targetY;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == 1) {
q.push({i, j});
dist[i][j] = 0;
paths[i][j] = 1;
}
if (grid[i][j] == 2) {
targetX = i;
targetY = j;
}
}
}
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == -1) continue;
if (dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
paths[nx][ny] = paths[x][y];
q.push({nx, ny});
} else if (dist[nx][ny] == dist[x][y] + 1) {
paths[nx][ny] += paths[x][y];
}
}
}
return paths[targetX][targetY];
}
31. Stock Trading with Limited Transactions
State machine dynamic programming approach to maximize profit with a limited number of transactions using separate tables for holding and not holding stocks.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> prices(n);
for (int i = 0; i < n; ++i) cin >> prices[i];
k = min(k, n / 2);
vector<vector<int>> hold(n + 1, vector<int>(k + 1, INT_MIN));
vector<vector<int>> cash(n + 1, vector<int>(k + 1, 0));
hold[0][0] = -prices[0];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
hold[i][j] = max(hold[i - 1][j], cash[i - 1][j] - prices[i - 1]);
cash[i][j] = cash[i - 1][j];
if (j > 0)
cash[i][j] = max(cash[i][j], hold[i - 1][j - 1] + prices[i - 1]);
}
}
int result = 0;
for (int j = 0; j <= k; ++j)
result = max(result, cash[n][j]);
cout << result << endl;
return 0;
}
32. Stock Trading Problem Summary
Summarize key approaches for stock trading problems: greedy for single transaction, state machine DP for limited transactions, and cumulative gains for unlimited transactions.
class Solution {
public:
int maxProfitSingle(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price);
maxProfit = max(maxProfit, price - minPrice);
}
return maxProfit;
}
int maxProfitUnlimited(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); ++i)
if (prices[i] > prices[i - 1])
profit += prices[i] - prices[i - 1];
return profit;
}
};