Question 1: Max Subset XOR with Limit

Problem Statement:

Dev loves XOR operations. He has an array A of N elements, and he wants to select at most K
elements from it (not necessarily consecutive) to maximize the XOR value of the selected elements.

Your task is to help Dev find the maximum possible XOR value he can get by selecting at most K
elements.

Input Format:

The first line contains two integers N and K.

The second line contains N space-separated integers representing the array A.

Constraints:

 1 ≤ N ≤ 100

 1≤K≤N

 1 ≤ A[i] ≤ 10⁶

Sample Input 1:

42

2468

Sample Output 1:

14

Explanation:
Choosing 2 and 8 gives 2 ^ 8 = 10.
Choosing 6 and 8 gives 6 ^ 8 = 14 — this is the maximum possible.

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int maxSubsetXOR(vector<int>& arr, int K) {

int N = arr.size();

int maxXOR = 0;
 for (int mask = 0; mask < (1 << N); ++mask) {

int cnt = __builtin_popcount(mask);

if (cnt > K) continue;

int currXOR = 0;

for (int i = 0; i < N; ++i) {

if (mask & (1 << i)) {

currXOR ^= arr[i];

maxXOR = max(maxXOR, currXOR);

return maxXOR;

int main() {

int N, K;

cin >> N >> K;

vector<int> A(N);

for (int i = 0; i < N; ++i)

cin >> A[i];

cout << maxSubsetXOR(A, K) << endl;

return 0;

Question 2: Xor-Sum vs Range

Problem Statement:

Sania gave you an array A of length N and a number K. She defined a function:

XorSum(x) = (x XOR A[0]) + (x XOR A[1]) + ... + (x XOR A[N-1])

Your task is to find an integer x in the range [0, K] that maximizes XorSum(x).

Input Format:

The first line contains two integers N and K.

The next line contains N space-separated integers A[i].

Constraints:

 1 ≤ N ≤ 10⁵

 0 ≤ K ≤ 10⁹

 0 ≤ A[i] ≤ 10⁹

Sample Input 1:

37

163

Sample Output 1:

14

Explanation:
Try all values of x from 0 to 7.
At x = 4, (4^1 + 4^6 + 4^3) = 14 (maximum).

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, K;

cin >> N >> K;

vector<int> A(N);

unordered_map<int, int> bitCount;

for (int i = 0; i < N; ++i) {

cin >> A[i];

int x = A[i], b = 0;
 while (x) {

if (x & 1) bitCount[b]++;

x >>= 1;

b++;

int ans = 0, x = 0;

for (int i = 30; i >= 0; --i) {

int ones = bitCount[i], zeros = N - ones;

if ((1 << i) <= K && zeros > ones) {

x |= (1 << i);

int maxXorSum = 0;

for (int i = 0; i < N; ++i) {

maxXorSum += (x ^ A[i]);

cout << maxXorSum << endl;

return 0;

Question 3: Maximize XOR of Any Subarray

Problem Statement:

Aarav is playing with an array of integers. He wants to select a contiguous subarray from the array
such that the XOR of all the elements in that subarray is maximum.

You need to help Aarav find this maximum XOR value among all possible subarrays.

Input Format:
The first line contains an integer N.

The second line contains N space-separated integers representing the array A.

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ A[i] ≤ 10⁹

Sample Input 1:

1234

Sample Output 1:

Explanation:
The subarray [3,4] gives 3^4 = 7, which is the maximum possible.

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode {

TrieNode* child[2] = {nullptr, nullptr};

};

void insert(TrieNode* root, int num) {

TrieNode* node = root;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->child[bit])

node->child[bit] = new TrieNode();

node = node->child[bit];

}
int query(TrieNode* root, int num) {

TrieNode* node = root;

int maxXOR = 0;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (node->child[!bit]) {

maxXOR |= (1 << i);

node = node->child[!bit];

} else {

node = node->child[bit];

return maxXOR;

int main() {

int n;

cin >> n;

vector<int> A(n);

for (int i = 0; i < n; ++i) cin >> A[i];

TrieNode* root = new TrieNode();

insert(root, 0);

int result = 0, prefixXOR = 0;

for (int i = 0; i < n; ++i) {

prefixXOR ^= A[i];

result = max(result, query(root, prefixXOR));

insert(root, prefixXOR);

}
 cout << result << endl;

return 0;

Question 4: Maximum XOR Pair in Array

Problem Statement:

Meher has a list of integers. She wants to choose any two distinct numbers from the list such that
their XOR is maximized.

Can you help Meher find the maximum XOR value possible between any pair of numbers from the
list?

Input Format:

The first line contains an integer N.

The second line contains N space-separated integers.

Constraints:

 2 ≤ N ≤ 10⁵

 0 ≤ A[i] ≤ 10⁹

Sample Input 1:

8 1 2 12

Sample Output 1:

14

Explanation:
8 ^ 6 = 14 is the maximum XOR among all pairs.

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode {
 TrieNode* child[2] = {nullptr, nullptr};

};

void insert(TrieNode* root, int num) {

TrieNode* node = root;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->child[bit])

node->child[bit] = new TrieNode();

node = node->child[bit];

int getMaxXOR(TrieNode* root, int num) {

TrieNode* node = root;

int maxXOR = 0;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (node->child[!bit]) {

maxXOR |= (1 << i);

node = node->child[!bit];

} else {

node = node->child[bit];

return maxXOR;

int main() {

int n;

cin >> n;
 vector<int> A(n);

for (int i = 0; i < n; ++i) cin >> A[i];

TrieNode* root = new TrieNode();

insert(root, A[0]);

int maxResult = 0;

for (int i = 1; i < n; ++i) {

maxResult = max(maxResult, getMaxXOR(root, A[i]));

insert(root, A[i]);

cout << maxResult << endl;

return 0;

Question 5: Equal XOR Partition

Problem Statement:

Isha has an array of integers. She wants to divide the array into two non-overlapping subsets such
that the XOR of both subsets is the same.

Your task is to determine whether such a partition is possible or not.

Input Format:

The first line contains an integer N.

The second line contains N space-separated integers.

Constraints:

 1 ≤ N ≤ 1000

 1 ≤ A[i] ≤ 10⁶

Sample Input 1:

4
1230

Sample Output 1:

YES

Explanation:
One possible partition: {1, 2, 3} and {0}
1^2^3 = 0 and 0^0 = 0.

Sample Input 2:

124

Sample Output 2:

NO

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N;

cin >> N;

vector<int> A(N);

for (int i = 0; i < N; ++i)

cin >> A[i];

int totalXOR = 0;

for (int i = 0; i < N; ++i)

totalXOR ^= A[i];

if (totalXOR == 0)

cout << "YES" << endl;

else

cout << "NO" << endl;

 return 0;

Question 6: Minimize XOR With Limit

Problem Statement:

Kabir has an integer array and a limit value L. He wants to choose a number X such that 0 ≤ X ≤ L and
XOR it with each array element. His goal is to minimize the total XOR sum.

Your task is to find the value of X (in the range [0, L]) that gives the minimum XOR-sum.

Input Format:

First line contains two integers N and L.

Second line contains N space-separated integers A[i].

Constraints:

 1 ≤ N ≤ 10⁵

 0 ≤ L ≤ 10⁹

 0 ≤ A[i] ≤ 10⁹

Sample Input 1:

37

231

Sample Output 1:

Explanation:
Try all values x from 0 to 7. Minimum total XOR-sum occurs at x = 3.

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int xorSum(vector<int>& A, int x) {

int total = 0;
 for (int a : A)

total += (a ^ x);

return total;

int main() {

int N, L;

cin >> N >> L;

vector<int> A(N);

for (int i = 0; i < N; ++i)

cin >> A[i];

int result = 0, minSum = INT_MAX;

for (int x = 0; x <= L; ++x) {

int curr = xorSum(A, x);

if (curr < minSum) {

minSum = curr;

result = x;

cout << result << endl;

return 0;

Question 7: XOR Game with Constraints

Problem Statement:

In the land of Bitsaria, a game is played using an array of integers. The player is allowed to pick any
subset of elements such that:

 No two picked elements are adjacent.

  The total number of picked elements does not exceed N / 2.

The objective is to maximize the XOR of the selected subset.

Can you help the player determine the maximum XOR achievable?

Input Format:

First line: Integer N (number of elements)

Second line: N space-separated integers

Constraints:

 2 ≤ N ≤ 1000 (even)

 1 ≤ A[i] ≤ 10⁶

Sample Input 1:

382519

Sample Output 1:

15

Explanation:
Pick elements [8, 5, 9] (positions 1, 3, 5 – not adjacent). 8^5^9 = 15

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int maxXOR(vector<int>& A, int i, int count, int limit, int xorVal, vector<vector<int>>& dp) {

if (i >= A.size() || count > limit)

return xorVal;

if (dp[i][count] != -1)

return dp[i][count];

int include = xorVal;

 if (count < limit)

include = maxXOR(A, i + 2, count + 1, limit, xorVal ^ A[i], dp);

int exclude = maxXOR(A, i + 1, count, limit, xorVal, dp);

return dp[i][count] = max(include, exclude);

int main() {

int N;

cin >> N;

vector<int> A(N);

for (int i = 0; i < N; ++i)

cin >> A[i];

vector<vector<int>> dp(N + 1, vector<int>(N / 2 + 1, -1));

cout << maxXOR(A, 0, 0, N / 2, 0, dp) << endl;

return 0;

Question 8: XOR Triplets Count

Problem Statement:

You are given an array A of size N. A triplet (i, j, k) is valid if i < j < k and A[i] ^ A[j] ^ A[k] == 0.

Find the total number of valid triplets satisfying the condition.

Input Format:

First line: Integer N

Second line: N space-separated integers

Constraints:

 1 ≤ N ≤ 500
  0 ≤ A[i] ≤ 10⁶

Sample Input 1:

12301

Sample Output 1:

Explanation:
Triplets that satisfy: (0,1,2) → 1^2^3 = 0
and (1,2,3) → 2^3^0 = 1

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N;

cin >> N;

vector<int> A(N);

for (int i = 0; i < N; ++i)

cin >> A[i];

int count = 0;

for (int i = 0; i < N; ++i) {

for (int j = i + 1; j < N; ++j) {

for (int k = j + 1; k < N; ++k) {

if ((A[i] ^ A[j] ^ A[k]) == 0)

count++;

}
 cout << count << endl;

return 0;

Question 11: Minimum Jumps to Reach End (Greedy)

Problem Statement:

Priya is stuck in a game level represented by an array A, where each value A[i] indicates the
maximum number of steps she can jump forward from position i. She starts from index 0.

Find the minimum number of jumps required to reach the end of the array. If it is not possible,
return -1.

Input Format:

First line: Integer N (size of array)

Second line: N space-separated integers

Constraints:

 1 ≤ N ≤ 10⁵

 0 ≤ A[i] ≤ 10⁵

Sample Input 1:

231142

Sample Output 1:

Explanation:
Jump from 0 → 1 → 4 → end (3 jumps)

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int minJumps(vector<int>& A) {

int n = A.size();
 if (n <= 1) return 0;

if (A[0] == 0) return -1;

int jumps = 1, farthest = A[0], currEnd = A[0];

for (int i = 1; i < n; ++i) {

if (i == n - 1) return jumps;

farthest = max(farthest, i + A[i]);

if (i == currEnd) {

jumps++;

currEnd = farthest;

if (currEnd <= i) return -1;

return -1;

int main() {

int N;

cin >> N;

vector<int> A(N);

for (int i = 0; i < N; ++i) cin >> A[i];

cout << minJumps(A) << endl;

return 0;

Question 12: Maximum Sum of Subarray of Size K (Sliding Window)

Problem Statement:

Ravi wants to invest in K consecutive stocks for K days to get the maximum profit. The array A
contains the profit values for N days.

Find the maximum sum of any subarray of size K.

Input Format:

First line: Two integers N and K

Second line: N space-separated integers

Constraints:

 1 ≤ N ≤ 10⁶

 1≤K≤N

 -10⁴ ≤ A[i] ≤ 10⁴

Sample Input 1:

73

2151326

Sample Output 1:

10

Explanation:
Subarray [5,1,3] has max sum 9. Subarray [3,2,6] has sum 11 (maximum).

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, K;

cin >> N >> K;

vector<int> A(N);

for (int i = 0; i < N; ++i) cin >> A[i];

int currSum = 0, maxSum = INT_MIN;

for (int i = 0; i < K; ++i)

currSum += A[i];

maxSum = currSum;
 for (int i = K; i < N; ++i) {

currSum = currSum - A[i - K] + A[i];

maxSum = max(maxSum, currSum);

cout << maxSum << endl;

return 0;

Question 13: Allocate Minimum Pages (Binary Search + Greedy)

Problem Statement:

A school has N books, with pages given in an array A[]. There are M students, and books must be
allocated in contiguous blocks.

Each student gets at least one book, and each book must be assigned to exactly one student.

Your task is to allocate the books so that the maximum number of pages assigned to any student is
minimized.

Input Format:

First line: Two integers N and M

Second line: N space-separated integers representing pages in books

Constraints:

 1 ≤ N ≤ 10⁵

 1≤M≤N

 1 ≤ A[i] ≤ 10⁹

Sample Input 1:

42

12 34 67 90

Sample Output 1:

113
Explanation:
One optimal way: [12, 34, 67] and [90] → Max pages = 113

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

bool isPossible(vector<int>& A, int N, int M, int mid) {

int students = 1, sum = 0;

for (int i = 0; i < N; ++i) {

if (A[i] > mid) return false;

if (sum + A[i] > mid) {

students++;

sum = A[i];

} else {

sum += A[i];

return students <= M;

int main() {

int N, M;

cin >> N >> M;

vector<int> A(N);

for (int i = 0; i < N; ++i)

cin >> A[i];

int low = *max_element(A.begin(), A.end());

int high = accumulate(A.begin(), A.end(), 0);

int result = high;

 while (low <= high) {

int mid = (low + high) / 2;

if (isPossible(A, N, M, mid)) {

result = mid;

high = mid - 1;

} else {

low = mid + 1;

cout << result << endl;

return 0;

Question 14: Shortest Path in Binary Matrix (BFS)

Problem Statement:

You are given a N x N binary matrix grid where:

 0 represents a free cell

 1 represents a blocked cell

You can move in 8 directions (including diagonals).

Find the shortest path from top-left (0, 0) to bottom-right (N-1, N-1). Return the length of the
shortest path, or -1 if no path exists.

Input Format:

First line: Integer N

Next N lines: Each line has N space-separated integers (0 or 1)

Constraints:

 1 ≤ N ≤ 100

 grid[i][j] ∈ {0,1}
Sample Input 1:

010

000

100

Sample Output 1:

Explanation:
One path is (0,0) → (1,0) → (1,1) → (1,2) → (2,2)

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int shortestPath(vector<vector<int>>& grid) {

int N = grid.size();

if (grid[0][0] == 1 || grid[N - 1][N - 1] == 1)

return -1;

queue<tuple<int, int, int>> q;

q.push({0, 0, 1});

vector<vector<bool>> visited(N, vector<bool>(N, false));

visited[0][0] = true;

vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};

vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

while (!q.empty()) {

auto [x, y, dist] = q.front(); q.pop();

if (x == N - 1 && y == N - 1) return dist;

 for (int d = 0; d < 8; ++d) {

int nx = x + dx[d], ny = y + dy[d];

if (nx >= 0 && ny >= 0 && nx < N && ny < N &&

!visited[nx][ny] && grid[nx][ny] == 0) {

visited[nx][ny] = true;

q.push({nx, ny, dist + 1});

return -1;

int main() {

int N;

cin >> N;

vector<vector<int>> grid(N, vector<int>(N));

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

cin >> grid[i][j];

cout << shortestPath(grid) << endl;

return 0;

Question 15: Coin Change Ways (DP)

Problem Statement:

Arjun is at a shop and wants to pay a total amount X using unlimited coins of certain denominations
available in an array coins[].

He wants to find the total number of ways he can make the payment using any number of coins.

Input Format:
First line: Two integers N (number of coin types) and X (target amount)

Second line: N space-separated integers representing coin denominations

Constraints:

 1 ≤ N ≤ 100

 1 ≤ X ≤ 10⁴

 1 ≤ coins[i] ≤ 100

Sample Input 1:

34

123

Sample Output 1:

Explanation:
The 4 ways to make 4 are:
1+1+1+1, 1+1+2, 2+2, 1+3

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main() {

int N, X;

cin >> N >> X;

vector<int> coins(N);

for (int i = 0; i < N; ++i) cin >> coins[i];

vector<int> dp(X + 1, 0);

dp[0] = 1;

for (int c : coins) {

for (int i = c; i <= X; ++i) {

 dp[i] = (dp[i] + dp[i - c]) % MOD;

cout << dp[X] << endl;

return 0;

Question 16: Max Meetings in One Room (Greedy)

Problem Statement:

Sanya is the in-charge of a conference room. She receives N meeting requests with their start and
end times. Only one meeting can be held at a time.

She wants to schedule as many meetings as possible without overlaps.

Help her maximize the number of non-overlapping meetings.

Input Format:

First line: Integer N

Next N lines: Two space-separated integers start and end time of each meeting

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ start < end ≤ 10⁹

Sample Input 1:

12

34

06

57

89

59

Sample Output 1:

4
Explanation:
Max meetings = 4
Possible meetings: (1-2), (3-4), (5-7), (8-9)

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

bool compare(pair<int, int>& a, pair<int, int>& b) {

return a.second < b.second;

int main() {

int N;

cin >> N;

vector<pair<int, int>> meetings(N);

for (int i = 0; i < N; ++i)

cin >> meetings[i].first >> meetings[i].second;

sort(meetings.begin(), meetings.end(), compare);

int count = 1;

int lastEnd = meetings[0].second;

for (int i = 1; i < N; ++i) {

if (meetings[i].first > lastEnd) {

count++;

lastEnd = meetings[i].second;

}
 cout << count << endl;

return 0;

Question 17: N-Queens Problem (Backtracking)

Problem Statement:

Queen Leia needs to place N queens on an N x N chessboard such that:

 No two queens attack each other (i.e., no two queens share the same row, column, or
diagonal).

Your task is to count the total number of possible valid arrangements.

Input Format:

One integer N (size of board and number of queens)

Constraints:

 1 ≤ N ≤ 12

Sample Input 1:

Sample Output 1:

Explanation:
There are two valid ways to place 4 queens on a 4x4 board.

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int countSolutions = 0;

void solve(int row, int n, vector<int>& col, vector<int>& diag1, vector<int>& diag2) {

if (row == n) {

countSolutions++;
 return;

for (int c = 0; c < n; ++c) {

if (col[c] || diag1[row - c + n - 1] || diag2[row + c])

continue;

col[c] = diag1[row - c + n - 1] = diag2[row + c] = 1;

solve(row + 1, n, col, diag1, diag2);

col[c] = diag1[row - c + n - 1] = diag2[row + c] = 0;

int main() {

int N;

cin >> N;

vector<int> col(N, 0), diag1(2 * N - 1, 0), diag2(2 * N - 1, 0);

solve(0, N, col, diag1, diag2);

cout << countSolutions << endl;

return 0;

Question 18: Count Valid Binary Strings (Combinatorics + DP)

Problem Statement:

Aryan is constructing binary strings of length N such that no two consecutive 1s appear.

Find the total number of such binary strings possible.

Input Format:

One integer N

Constraints:

 1 ≤ N ≤ 10⁵

Sample Input 1:
3

Sample Output 1:

Explanation:
The valid strings of length 3:
000, 001, 010, 100, 101

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main() {

int N;

cin >> N;

long long a = 1, b = 1, c;

for (int i = 2; i <= N; ++i) {

c = (a + b) % MOD;

a = b;

b = c;

cout << b << endl;

return 0;

Question 19: Detect Cycle in Directed Graph (DFS + Recursion Stack)

Problem Statement:

Yusuf is analyzing a dependency system where each task is represented as a node in a directed
graph. A cycle in the graph means a deadlock.

Write a program to detect if there's any cycle in the graph.

Input Format:

First line: Two integers N (nodes) and M (edges)

Next M lines: Two integers u and v (u → v is a directed edge)

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ M ≤ 10⁵

 1 ≤ u, v ≤ N

Sample Input 1:

44

12

23

34

42

Sample Output 1:

YES

Explanation: There is a cycle: 2 → 3 → 4 → 2

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

bool dfs(int node, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& recStack) {

visited[node] = recStack[node] = true;

for (int neighbor : graph[node]) {

if (!visited[neighbor] && dfs(neighbor, graph, visited, recStack))

return true;

else if (recStack[neighbor])

return true;

}
 recStack[node] = false;

return false;

int main() {

int N, M;

cin >> N >> M;

vector<vector<int>> graph(N + 1);

for (int i = 0; i < M; ++i) {

int u, v;

cin >> u >> v;

graph[u].push_back(v);

vector<bool> visited(N + 1, false), recStack(N + 1, false);

for (int i = 1; i <= N; ++i) {

if (!visited[i] && dfs(i, graph, visited, recStack)) {

cout << "YES" << endl;

return 0;

cout << "NO" << endl;

return 0;

Question 20: Count Occurrences of Pattern in String (KMP Algorithm)

Problem Statement:

Anjali has a string S and a pattern P. She wants to know how many times the pattern P occurs in S as
a substring (even overlapping allowed).

Use an efficient algorithm like KMP (Knuth-Morris-Pratt) to solve it in linear time.

Input Format:

First line: String S

Second line: String P

Constraints:

 1 ≤ |S|, |P| ≤ 10⁵

 Both contain only lowercase English letters

Sample Input 1:

ababcabcabababc

ababc

Sample Output 1:

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

vector<int> computeLPS(string& P) {

int m = P.length();

vector<int> lps(m, 0);

int len = 0;

for (int i = 1; i < m; ) {

if (P[i] == P[len])

lps[i++] = ++len;

else if (len != 0)

len = lps[len - 1];

else

lps[i++] = 0;

return lps;
}

int KMP(string& S, string& P) {

int n = S.length(), m = P.length();

vector<int> lps = computeLPS(P);

int i = 0, j = 0, count = 0;

while (i < n) {

if (S[i] == P[j]) {

i++; j++;

if (j == m) {

count++;

j = lps[j - 1];

} else if (i < n && S[i] != P[j]) {

if (j != 0)

j = lps[j - 1];

else

i++;

return count;

int main() {

string S, P;

cin >> S >> P;

cout << KMP(S, P) << endl;

return 0;

}
Question 21: Cargo Route Optimization (Graph + Dijkstra + Priority Queue)

Problem Statement:

An international cargo company wants to find the cheapest route to ship goods from city A to city B.
The cities are connected by directed roads, each with a cost.

You are given a map with N cities and M roads. You need to find the minimum cost to travel from city
S to city D.

Input Format:

First line: Three integers N, M, S, D

Next M lines: Each line contains three integers: U, V, W

- Road from U to V with cost W

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ M ≤ 2×10⁵

 1 ≤ U, V ≤ N

 1 ≤ W ≤ 10⁴

 1 ≤ S, D ≤ N

Sample Input:

5615

122

234

1 3 10

343

451

2 5 20

Sample Output:

10

Explanation:
Path: 1 → 2 → 3 → 4 → 5, total cost = 2 + 4 + 3 + 1 = 10
C++ Solution:

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

int main() {

int N, M, S, D;

cin >> N >> M >> S >> D;

vector<vector<pii>> graph(N + 1);

for (int i = 0; i < M; ++i) {

int U, V, W;

cin >> U >> V >> W;

graph[U].push_back({V, W});

vector<int> dist(N + 1, INT_MAX);

priority_queue<pii, vector<pii>, greater<pii>> pq;

dist[S] = 0;

pq.push({0, S});

while (!pq.empty()) {

auto [d, u] = pq.top(); pq.pop();

if (d > dist[u]) continue;

for (auto [v, w] : graph[u]) {

if (dist[v] > dist[u] + w) {

dist[v] = dist[u] + w;

pq.push({dist[v], v});

}
 }

cout << (dist[D] == INT_MAX ? -1 : dist[D]) << endl;

return 0;

Question 22: Lexicographically Smallest String After K Swaps (Greedy + Sorting)

Problem Statement:

Akira has a string S and an integer K. She can perform the following operation any number of times (≤
K times):

 Choose any two characters at indices i and j (0 ≤ i < j < length) and swap them.

Your task is to return the lexicographically smallest string that can be formed by at most K swaps.

Input Format:

First line: String S

Second line: Integer K

Constraints:

 1 ≤ |S| ≤ 1000

 0 ≤ K ≤ 10⁴

 S contains only lowercase English letters

Sample Input:

dcab

Sample Output:

bacd

Explanation:
Swap 'd' and 'b', then swap 'c' and 'a' → result = "bacd"

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

void kSwaps(string& s, int K) {

int n = s.length();

for (int i = 0; i < n && K > 0; ++i) {

char minChar = s[i];

int pos = i;

for (int j = i + 1; j < n && (j - i) <= K; ++j) {

if (s[j] < minChar) {

minChar = s[j];

pos = j;

for (int j = pos; j > i; --j)

swap(s[j], s[j - 1]);

K -= (pos - i);

cout << s << endl;

int main() {

string S;

int K;

cin >> S >> K;

kSwaps(S, K);

return 0;

Question 23: Palindrome Partitioning (Backtracking + DP)

Problem Statement:

Naina wants to divide a string S into the minimum number of palindromic substrings. Each substring
must itself be a palindrome.

Your task is to return the minimum number of cuts needed to partition S into such substrings.

Input Format:

One line: String S

Constraints:

 1 ≤ |S| ≤ 1000

 S contains only lowercase letters

Sample Input 1:

aab

Sample Output 1:

Explanation:
"a | ab" → Not valid (ab is not palindrome)
"a | a | b" → 2 cuts (valid)
"a | ab" or "aa | b" → 1 cut (valid, minimum)

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

bool isPalindrome(string& s, int i, int j) {

while (i < j) {

if (s[i++] != s[j--]) return false;

return true;

int minCuts(string& s) {
 int n = s.length();

vector<int> dp(n + 1, 0);

for (int i = 0; i < n; ++i) dp[i] = i;

for (int i = 0; i < n; ++i) {

for (int j = 0; j <= i; ++j) {

if (isPalindrome(s, j, i)) {

dp[i] = j == 0 ? 0 : min(dp[i], dp[j - 1] + 1);

return dp[n - 1];

int main() {

string S;

cin >> S;

cout << minCuts(S) << endl;

return 0;

Question 24: Word Search Puzzle (Backtracking + DFS)

Problem Statement:

Sara is playing a word search game on a 2D board. Each cell contains a lowercase letter. You are given
a word, and you must check whether the word exists in the board by traversing horizontally or
vertically (not diagonally).

You can only use each cell once per word search.

Input Format:

First line: Two integers N and M (rows and columns)

Next N lines: Each line has M lowercase characters

Next line: Word to search

Constraints:

 1 ≤ N, M ≤ 20

 1 ≤ word length ≤ 1000

Sample Input:

34

abce

sfcs

adee

abcced

Sample Output:

YES

Explanation:
Word “abcced” is found by path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int N, M;

vector<vector<char>> board;

string word;

bool dfs(int i, int j, int index, vector<vector<bool>>& visited) {

if (index == word.length()) return true;

if (i < 0 || j < 0 || i >= N || j >= M || visited[i][j] || board[i][j] != word[index])

return false;

visited[i][j] = true;

bool found = dfs(i + 1, j, index + 1, visited) ||

 dfs(i - 1, j, index + 1, visited) ||

dfs(i, j + 1, index + 1, visited) ||

dfs(i, j - 1, index + 1, visited);

visited[i][j] = false;

return found;

int main() {

cin >> N >> M;

board = vector<vector<char>>(N, vector<char>(M));

for (int i = 0; i < N; ++i)

for (int j = 0; j < M; ++j)

cin >> board[i][j];

cin >> word;

vector<vector<bool>> visited(N, vector<bool>(M, false));

for (int i = 0; i < N; ++i)

for (int j = 0; j < M; ++j)

if (dfs(i, j, 0, visited)) {

cout << "YES" << endl;

return 0;

cout << "NO" << endl;

return 0;

Question 25: Longest Common Prefix using Trie

Problem Statement:

You are given a list of N strings. You must find the longest common prefix among them.
To solve this efficiently, implement a Trie (prefix tree).

Input Format:

First line: Integer N

Next N lines: Each line contains one lowercase string

Constraints:

 1 ≤ N ≤ 10⁴

 1 ≤ length of any string ≤ 1000

Sample Input:

flower

flow

flight

flame

Sample Output:

fl

Explanation:
All strings start with fl, which is the longest common prefix.

C++ Solution (with Trie):

#include <bits/stdc++.h>

using namespace std;

struct TrieNode {

TrieNode* children[26];

int count;

TrieNode() {

count = 0;

for (int i = 0; i < 26; i++) children[i] = nullptr;

 }

};

void insert(TrieNode* root, const string& word) {

TrieNode* node = root;

for (char c : word) {

int idx = c - 'a';

if (!node->children[idx])

node->children[idx] = new TrieNode();

node = node->children[idx];

node->count++;

string longestCommonPrefix(TrieNode* root, int totalWords) {

string prefix = "";

TrieNode* node = root;

while (true) {

int childCount = 0, index = -1;

for (int i = 0; i < 26; ++i) {

if (node->children[i]) {

if (node->children[i]->count == totalWords) {

childCount++;

index = i;

} else return prefix;

if (childCount != 1) break;

prefix += (char)(index + 'a');

node = node->children[index];

}
 return prefix;

int main() {

int N;

cin >> N;

TrieNode* root = new TrieNode();

vector<string> words(N);

for (int i = 0; i < N; ++i) {

cin >> words[i];

insert(root, words[i]);

cout << longestCommonPrefix(root, N) << endl;

return 0;

Question 26: Count Number of Subsets with Given XOR (Bitmask + DP)

Problem Statement:

Given an array A of N integers and a target value K, find the number of subsets whose XOR is equal
to K.

Input Format:

First line: Two integers N and K

Second line: N space-separated integers (array A)

Constraints:

 1 ≤ N ≤ 100

 0 ≤ A[i], K ≤ 1000

Sample Input:

46

1234
Sample Output:

Explanation:
Subsets with XOR = 6:

 {2, 4} → 2^4 = 6

 {1, 2, 3} → 1^2^3 = 0^3 = 3^3 = 0 → Not valid

 {1, 3, 4} → 1^3^4 = 6
So total = 2

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int countSubsetsWithXOR(vector<int>& A, int K) {

int n = A.size();

int maxXOR = 1024; // Since max A[i] is ≤ 1000

vector<vector<int>> dp(n + 1, vector<int>(maxXOR, 0));

dp[0][0] = 1;

for (int i = 1; i <= n; ++i) {

for (int j = 0; j < maxXOR; ++j) {

dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ A[i - 1]];

return dp[n][K];

int main() {

int N, K;

cin >> N >> K;

 vector<int> A(N);

for (int i = 0; i < N; ++i) cin >> A[i];

cout << countSubsetsWithXOR(A, K) << endl;

return 0;

Question 27: 0/1 Knapsack – Maximum Profit

Problem Statement:

A logistics company wants to maximize profit by choosing which items to load into a truck. Each item
has a weight and a profit. The truck can carry at most W weight.

You need to pick items such that:

 The total weight ≤ W

 The total profit is maximized

 Each item can be selected at most once (0/1 Knapsack)

Input Format:

First line: Two integers N and W (number of items and max weight)

Next N lines: Each line contains two integers: weight[i] and profit[i]

Constraints:

 1 ≤ N ≤ 1000

 1 ≤ W ≤ 10⁴

 1 ≤ weight[i], profit[i] ≤ 10⁴

Sample Input:

4 10

5 10

4 40

6 30

3 50

Sample Output:
90

Explanation:
Choose items 2 and 4 → Total weight = 4+3 = 7, Total profit = 40+50 = 90

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, W;

cin >> N >> W;

vector<int> wt(N), val(N);

for (int i = 0; i < N; ++i)

cin >> wt[i] >> val[i];

vector<int> dp(W + 1, 0);

for (int i = 0; i < N; ++i) {

for (int w = W; w >= wt[i]; --w) {

dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

cout << dp[W] << endl;

return 0;

Question 28: Bitmask Assignment Problem (DP + Bitmask)

Problem Statement:

There are N workers and N jobs. Each worker can do one job, and each job can be assigned to only
one worker.
You are given a cost matrix where cost[i][j] is the cost for worker i to do job j. Your task is to assign
one job to each worker so that the total cost is minimized.

Use bitmasking + DP for optimization.

Input Format:

First line: Integer N

Next N lines: Each line has N integers (cost[i][j])

Constraints:

 1 ≤ N ≤ 20

 1 ≤ cost[i][j] ≤ 100

Sample Input:

927

643

581

Sample Output:

13

Explanation:
Worker 0 → job 1 (cost 2)
Worker 1 → job 2 (cost 3)
Worker 2 → job 0 (cost 5)
Total = 2 + 3 + 5 = 10

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int N;

int cost[21][21];

int dp[1 << 21];

int solve(int mask, int idx) {

 if (idx == N) return 0;

if (dp[mask] != -1) return dp[mask];

int res = INT_MAX;

for (int j = 0; j < N; ++j) {

if (!(mask & (1 << j))) {

res = min(res, cost[idx][j] + solve(mask | (1 << j), idx + 1));

return dp[mask] = res;

int main() {

cin >> N;

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

cin >> cost[i][j];

memset(dp, -1, sizeof(dp));

cout << solve(0, 0) << endl;

return 0;

Question 29: Unique Paths with Obstacles (Matrix DP)

Problem Statement:

A robot is placed in a grid with m x n cells. It starts at the top-left and wants to reach the bottom-
right. Some cells have obstacles (1), and others are free (0).

Only right or down moves are allowed. Find the number of unique paths avoiding obstacles.

Input Format:

First line: Two integers m, n

Next m lines: n integers (0 for empty, 1 for obstacle)

Constraints:

 1 ≤ m, n ≤ 100

Sample Input:

33

000

010

000

Sample Output:

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

vector<vector<int>> grid(m, vector<int>(n));

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

cin >> grid[i][j];

vector<vector<int>> dp(m, vector<int>(n, 0));

if (grid[0][0] == 0) dp[0][0] = 1;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

if (grid[i][j] == 0) {
 if (i > 0) dp[i][j] += dp[i - 1][j];

if (j > 0) dp[i][j] += dp[i][j - 1];

cout << dp[m - 1][n - 1] << endl;

Question 30: Nim Game (Game Theory + XOR)

Problem Statement:

Given N piles of stones, with the number of stones in each pile as A[i], determine who will win the
Nim Game if both play optimally.

 First player starts.

 The player who removes the last stone wins.

Input Format:

First line: Integer N

Next line: N space-separated integers

Output:
Print "First" if first player will win, else "Second"

Sample Input:

145

Sample Output:

First

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, x = 0, a;
 cin >> N;

for (int i = 0; i < N; ++i) {

cin >> a;

x ^= a;

cout << (x == 0 ? "Second" : "First") << endl;

Question 31: Hamiltonian Path in Graph (Bitmask + DP)

Problem Statement:

Given a directed graph with N nodes, find if there's a Hamiltonian Path (a path that visits every node
exactly once).

Use Bitmask + DP for optimization.

Input Format:

First line: N (number of nodes), M (edges)

Next M lines: Two integers u v (u → v)

Constraints:

 1 ≤ N ≤ 20

 0 ≤ M ≤ N*(N-1)

Sample Input:

44

12

23

34

13

Sample Output:

YES

C++ Solution:
#include <bits/stdc++.h>

using namespace std;

int N, M;

vector<vector<int>> adj;

vector<vector<int>> dp;

bool isHamiltonian() {

dp.assign(1 << N, vector<int>(N, 0));

for (int i = 0; i < N; i++) dp[1 << i][i] = 1;

for (int mask = 1; mask < (1 << N); mask++) {

for (int u = 0; u < N; u++) {

if (!(mask & (1 << u)) || !dp[mask][u]) continue;

for (int v : adj[u]) {

if (!(mask & (1 << v))) {

dp[mask | (1 << v)][v] = 1;

for (int i = 0; i < N; i++)

if (dp[(1 << N) - 1][i]) return true;

return false;

int main() {

cin >> N >> M;

adj.assign(N, {});
 for (int i = 0; i < M; ++i) {

int u, v; cin >> u >> v;

adj[u - 1].push_back(v - 1);

cout << (isHamiltonian() ? "YES" : "NO") << endl;

Question 32: Job Scheduling for Maximum Profit (Greedy + Sorting)

Problem Statement:

You are given jobs with start time, end time, and profit. Schedule non-overlapping jobs to get
maximum total profit.

Input Format:

First line: Integer N

Next N lines: start end profit

Constraints:

 1 ≤ N ≤ 10⁴

 1 ≤ start, end ≤ 10⁵

 1 ≤ profit ≤ 10⁴

Sample Input:

1 3 50

3 5 20

6 19 100

2 100 200

Sample Output:

250

C++ Solution (Binary Search + DP):

#include <bits/stdc++.h>
using namespace std;

struct Job {

int start, end, profit;

};

bool cmp(Job a, Job b) {

return a.end < b.end;

int main() {

int N;

cin >> N;

vector<Job> jobs(N);

for (int i = 0; i < N; ++i)

cin >> jobs[i].start >> jobs[i].end >> jobs[i].profit;

sort(jobs.begin(), jobs.end(), cmp);

vector<int> dp(N);

dp[0] = jobs[0].profit;

for (int i = 1; i < N; ++i) {

int incl = jobs[i].profit;

int l = -1, r = i - 1;

while (l <= r) {

int m = (l + r) / 2;

if (jobs[m].end <= jobs[i].start) l = m + 1;

else r = m - 1;

if (r != -1) incl += dp[r];

 dp[i] = max(dp[i - 1], incl);

cout << dp[N - 1] << endl;

Question 33: Expression Evaluation (Recursion + Memoization)

Problem Statement:

Given a string S of digits and operators (+, -, *), return all possible results from computing the
expression with different valid parentheses placement.

Input Format:

One line: expression string (like 2*3-4*5)

Output:
All possible results (order doesn’t matter)

Sample Input:

2*3-4*5

Sample Output:

-34 -14 -10 10

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, vector<int>> memo;

vector<int> diffWaysToCompute(string input) {

if (memo.count(input)) return memo[input];

vector<int> res;

for (int i = 0; i < input.length(); i++) {

 if (ispunct(input[i])) {

auto left = diffWaysToCompute(input.substr(0, i));

auto right = diffWaysToCompute(input.substr(i + 1));

for (int a : left)

for (int b : right) {

if (input[i] == '+') res.push_back(a + b);

else if (input[i] == '-') res.push_back(a - b);

else if (input[i] == '*') res.push_back(a * b);

if (res.empty()) res.push_back(stoi(input));

return memo[input] = res;

int main() {

string expr;

cin >> expr;

auto results = diffWaysToCompute(expr);

for (int r : results) cout << r << " ";

cout << endl;

Question 34: Tree DP – Maximum Weight Independent Set

Problem Statement:

You are given a tree with N nodes, each having a weight. You need to find the maximum sum of
weights of a subset of nodes such that no two adjacent nodes are both chosen.

Input Format:
First line: Integer N

Second line: N integers (weights of each node from 1 to N)

Next N-1 lines: Two integers u, v (edge between u and v)

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ weight[i] ≤ 10⁴

Sample Input:

12345

12

13

34

35

Sample Output:

11

Explanation:
Choose nodes 2, 4, and 5 → sum = 2 + 4 + 5 = 11

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> tree;

vector<int> weight;

vector<vector<int>> dp;

void dfs(int node, int parent) {

dp[node][0] = 0;

dp[node][1] = weight[node];
 for (int child : tree[node]) {

if (child == parent) continue;

dfs(child, node);

dp[node][0] += max(dp[child][0], dp[child][1]);

dp[node][1] += dp[child][0];

int main() {

int N;

cin >> N;

weight.resize(N + 1);

tree.resize(N + 1);

dp.assign(N + 1, vector<int>(2));

for (int i = 1; i <= N; ++i) cin >> weight[i];

for (int i = 0; i < N - 1; ++i) {

int u, v; cin >> u >> v;

tree[u].push_back(v);

tree[v].push_back(u);

dfs(1, 0);

cout << max(dp[1][0], dp[1][1]) << endl;

Question 35: Segment Tree – Range Maximum Query

Problem Statement:

You're given an array of size N, and you need to answer Q queries. Each query gives two integers L
and R and asks for the maximum element in the range [L, R].
Input Format:

First line: N Q

Second line: N space-separated integers

Next Q lines: two integers L R

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ Q ≤ 10⁵

 1 ≤ A[i] ≤ 10⁹

 0≤L≤R<N

Sample Input:

53

13524

13

02

24

Sample Output:

C++ Solution (Segment Tree):

#include <bits/stdc++.h>

using namespace std;

vector<int> seg;

void build(vector<int>& a, int n) {

for (int i = 0; i < n; ++i) seg[n + i] = a[i];

for (int i = n - 1; i > 0; --i) seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

int query(int l, int r, int n) {

int res = INT_MIN;

for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {

if (l & 1) res = max(res, seg[l++]);

if (r & 1) res = max(res, seg[--r]);

return res;

int main() {

int N, Q;

cin >> N >> Q;

vector<int> A(N);

for (int& x : A) cin >> x;

seg.resize(2 * N);

build(A, N);

while (Q--) {

int L, R;

cin >> L >> R;

cout << query(L, R, N) << endl;

Question 36: DP on Strings – Longest Palindromic Subsequence

Problem Statement:

Given a string S, return the length of the longest subsequence that is also a palindrome.
Input Format:

One line: String S

Constraints:

 1 ≤ |S| ≤ 1000

Sample Input:

bbbab

Sample Output:

Explanation:
Longest palindromic subsequence is “bbbb”

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int longestPalinSubseq(string s) {

int n = s.length();

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int i = n - 1; i >= 0; --i) {

dp[i][i] = 1;

for (int j = i + 1; j < n; ++j) {

if (s[i] == s[j])

dp[i][j] = 2 + dp[i + 1][j - 1];

else

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

return dp[0][n - 1];

}

int main() {

string s;

cin >> s;

cout << longestPalinSubseq(s) << endl;

Question 37: Trie + Bitmask – Maximum XOR Pair

Problem Statement:

Given an array of N integers, find the maximum XOR of any two elements.

Input Format:

First line: Integer N

Second line: N space-separated integers

Constraints:

 1 ≤ N ≤ 10⁵

 0 ≤ A[i] ≤ 10⁹

Sample Input:

3 10 5 25

Sample Output:

28

C++ Solution (Trie):

#include <bits/stdc++.h>

using namespace std;

struct TrieNode {

TrieNode* child[2] = {nullptr};

};

void insert(TrieNode* root, int num) {

TrieNode* node = root;

for (int i = 31; i >= 0; --i) {

int b = (num >> i) & 1;

if (!node->child[b]) node->child[b] = new TrieNode();

node = node->child[b];

int findMaxXOR(TrieNode* root, int num) {

TrieNode* node = root;

int maxXor = 0;

for (int i = 31; i >= 0; --i) {

int b = (num >> i) & 1;

if (node->child[1 - b]) {

maxXor |= (1 << i);

node = node->child[1 - b];

} else {

node = node->child[b];

return maxXor;

int main() {

int N;

cin >> N;

vector<int> nums(N);

TrieNode* root = new TrieNode();

 for (int& x : nums) {

cin >> x;

insert(root, x);

int ans = 0;

for (int num : nums)

ans = max(ans, findMaxXOR(root, num));

cout << ans << endl;

Question 38: DP with Memoization – Minimum Jumps to End

Problem Statement:

You are given an array where each element represents the max number of steps you can take
forward from that position. Write a function to return the minimum number of jumps to reach the
end of the array (from index 0).

If not possible, return -1.

Input Format:

First line: Integer N

Second line: N space-separated integers

Constraints:

 1 ≤ N ≤ 10⁴

 0 ≤ A[i] ≤ N

Sample Input:

231142

Sample Output:

3
Explanation:
Jump: 0 → 1 → 4 → 5

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int minJumps(vector<int>& nums) {

int n = nums.size(), jumps = 0, end = 0, far = 0;

for (int i = 0; i < n - 1; ++i) {

far = max(far, i + nums[i]);

if (i == end) {

jumps++;

end = far;

return end >= n - 1 ? jumps : -1;

int main() {

int n;

cin >> n;

vector<int> A(n);

for (int& x : A) cin >> x;

cout << minJumps(A) << endl;

Question 39: Dijkstra’s Algorithm – Shortest Path in Weighted Graph

Problem Statement:

You are given a graph with N nodes and M edges, each edge has a weight. Find the shortest distance
from node 1 to every other node using Dijkstra's algorithm.
Input Format:

First line: N M

Next M lines: u v w (edge from u to v with weight w)

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ M ≤ 2*10⁵

 1 ≤ w ≤ 10⁴

Sample Input:

56

122

134

231

247

353

451

Sample Output:

02396

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {

int n, m;

cin >> n >> m;

vector<vector<pair<int,int>>> adj(n+1);

for (int i = 0; i < m; ++i) {

 int u,v,w; cin >> u >> v >> w;

adj[u].push_back({v, w});

adj[v].push_back({u, w});

vector<int> dist(n+1, INF);

dist[1] = 0;

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

pq.push({0, 1});

while (!pq.empty()) {

auto [d,u] = pq.top(); pq.pop();

if (d > dist[u]) continue;

for (auto [v, w] : adj[u]) {

if (dist[u] + w < dist[v]) {

dist[v] = dist[u] + w;

pq.push({dist[v], v});

for (int i = 1; i <= n; i++) cout << (dist[i] == INF ? -1 : dist[i]) << " ";

Question 40: Subset Sum Closest to Target (DP + Pruning)

Problem Statement:

Given an array A of N integers and a target sum K, find the maximum possible sum ≤ K by selecting a
subset of elements.

Input Format:
First line: N K

Next line: N integers

Constraints:

 1 ≤ N ≤ 100

 1 ≤ K ≤ 10⁵

 1 ≤ A[i] ≤ 10⁴

Sample Input:

59

3 34 4 12 5

Sample Output:

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, K;

cin >> N >> K;

vector<int> A(N);

for (int& x : A) cin >> x;

vector<bool> dp(K+1, false);

dp[0] = true;

for (int a : A)

for (int j = K; j >= a; --j)

dp[j] = dp[j] || dp[j - a];

for (int i = K; i >= 0; --i)

 if (dp[i]) {

cout << i << endl;

break;

Question 41: Sliding Window – Maximum Sum Subarray of Size K

Problem Statement:

Given an array and integer K, find the maximum sum of any contiguous subarray of size K.

Input Format:

First line: N K

Next line: N integers

Constraints:

 1 ≤ N ≤ 10⁵

 1≤K≤N

 -10⁴ ≤ A[i] ≤ 10⁴

Sample Input:

52

1 4 2 10 23

Sample Output:

33

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, K;

cin >> N >> K;

 vector<int> A(N);

for (int& x : A) cin >> x;

int sum = 0, maxSum = INT_MIN;

for (int i = 0; i < K; ++i) sum += A[i];

maxSum = sum;

for (int i = K; i < N; ++i) {

sum += A[i] - A[i - K];

maxSum = max(maxSum, sum);

cout << maxSum << endl;

Question 42: 2-Pointer Technique – Pair Sum Equals Target

Problem Statement:

Given a sorted array and a target sum, check if there exists a pair (i, j) such that arr[i] + arr[j] = target.

Input Format:

First line: N Target

Second line: N sorted integers

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ arr[i] ≤ 10⁹

Sample Input:

69

1 2 4 4 7 10

Sample Output:

YES
C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, target;

cin >> N >> target;

vector<int> A(N);

for (int& x : A) cin >> x;

int i = 0, j = N - 1;

while (i < j) {

int sum = A[i] + A[j];

if (sum == target) {

cout << "YES" << endl;

return 0;

} else if (sum < target) i++;

else j--;

cout << "NO" << endl;

Question 43: Bellman-Ford – Negative Cycle Detection

Problem Statement:

You are given a directed graph with N nodes and M edges. Some edge weights may be negative.
Determine if the graph contains a negative weight cycle.

Input Format:

First line: N M

Next M lines: u v w

Constraints:
  1 ≤ N ≤ 1000

 1 ≤ M ≤ 10⁴

 -10⁴ ≤ w ≤ 10⁴

Sample Input:

44

121

2 3 -1

3 4 -1

4 2 -1

Sample Output:

YES

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, M;

cin >> N >> M;

vector<tuple<int,int,int>> edges(M);

for (int i = 0; i < M; ++i) {

int u, v, w; cin >> u >> v >> w;

edges[i] = {u, v, w};

vector<int> dist(N + 1, 1e9);

dist[1] = 0;

for (int i = 1; i < N; ++i)

for (auto [u, v, w] : edges)

 if (dist[u] + w < dist[v])

dist[v] = dist[u] + w;

for (auto [u, v, w] : edges) {

if (dist[u] + w < dist[v]) {

cout << "YES" << endl;

return 0;

cout << "NO" << endl;

Question 44: Word Search in Grid (Backtracking + Recursion)

Problem Statement:

Given a 2D board and a word, check if the word exists in the grid.

 You can move horizontally or vertically in 4 directions.

 You cannot reuse the same cell twice.

Input Format:

First line: Two integers M N (rows and cols)

Next M lines: N characters (A-Z)

Last line: Target word

Constraints:

 1 ≤ M, N ≤ 10

 1 ≤ len(word) ≤ 100

Sample Input:

34

ABCE

SFCS
ADEE

ABCCED

Sample Output:

YES

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int m, n;

vector<vector<char>> board;

vector<vector<bool>> visited;

string word;

bool dfs(int i, int j, int index) {

if (index == word.size()) return true;

if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word[index]) return false;

visited[i][j] = true;

bool found = dfs(i + 1, j, index + 1) || dfs(i - 1, j, index + 1) ||

dfs(i, j + 1, index + 1) || dfs(i, j - 1, index + 1);

visited[i][j] = false;

return found;

int main() {

cin >> m >> n;

board.resize(m, vector<char>(n));

visited.resize(m, vector<bool>(n, false));

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

 cin >> board[i][j];

cin >> word;

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

if (dfs(i, j, 0)) {

cout << "YES";

return 0;

cout << "NO";

Question 45: Activity Selection (Greedy)

Problem Statement:

Given N activities with start and end times, find the maximum number of non-overlapping activities
you can perform.

Input Format:

First line: Integer N

Next N lines: Two integers start and end

Constraints:

 1 ≤ N ≤ 10⁵

 1 ≤ start < end ≤ 10⁹

Sample Input:

13

25

46

67
Sample Output:

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {

int N;

cin >> N;

vector<pair<int, int>> activities(N);

for (int i = 0; i < N; i++)

cin >> activities[i].second >> activities[i].first;

sort(activities.begin(), activities.end());

int count = 1, lastEnd = activities[0].first;

for (int i = 1; i < N; ++i) {

if (activities[i].second >= lastEnd) {

count++;

lastEnd = activities[i].first;

cout << count;

Question 46: Matrix Exponentiation – Fibonacci nth Term

Problem Statement:

Given an integer n, return the n-th Fibonacci number using Matrix Exponentiation in O(log n).
Input Format:

Single integer: n

Constraints:

 0 ≤ n ≤ 10⁹

Sample Input:

10

Sample Output:

55

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

typedef vector<vector<long long>> matrix;

matrix mul(matrix A, matrix B) {

matrix C(2, vector<long long>(2));

for (int i = 0; i < 2; ++i)

for (int j = 0; j < 2; ++j)

for (int k = 0; k < 2; ++k)

C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;

return C;

matrix power(matrix A, int n) {

matrix res = {{1, 0}, {0, 1}};

while (n) {

if (n & 1) res = mul(res, A);

A = mul(A, A);
 n >>= 1;

return res;

int main() {

int n;

cin >> n;

if (n == 0) {

cout << 0;

return 0;

matrix base = {{1, 1}, {1, 0}};

matrix res = power(base, n - 1);

cout << res[0][0];

Question 47: Number Theory – Count Coprimes ≤ N

Problem Statement:

Given n, find how many numbers from 1 to n are coprime with n using Euler’s Totient Function.

Input Format:

Single integer: n

Constraints:

 1 ≤ n ≤ 10⁶

Sample Input:

Sample Output:

6
C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int phi(int n) {

int res = n;

for (int p = 2; p * p <= n; ++p) {

if (n % p == 0) {

while (n % p == 0) n /= p;

res -= res / p;

if (n > 1) res -= res / n;

return res;

int main() {

int n;

cin >> n;

cout << phi(n);

Question 48: Bitmask DP – Traveling Salesman Problem (TSP)

Problem Statement:

Given a matrix dist[N][N] where dist[i][j] is the cost of going from city i to j, find the minimum cost to
visit all cities once and return to the starting city.

Input Format:

First line: Integer N

Next N lines: N integers (cost matrix)

Constraints:
  2 ≤ N ≤ 15

 1 ≤ dist[i][j] ≤ 1000

Sample Input:

0 10 15 20

10 0 35 25

15 35 0 30

20 25 30 0

Sample Output:

80

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int dp[1 << 15][15];

int dist[15][15];

int N;

int tsp(int mask, int pos) {

if (mask == (1 << N) - 1) return dist[pos][0];

if (dp[mask][pos] != -1) return dp[mask][pos];

int ans = INF;

for (int city = 0; city < N; city++) {

if ((mask & (1 << city)) == 0) {

int newAns = dist[pos][city] + tsp(mask | (1 << city), city);

ans = min(ans, newAns);

}
 }

return dp[mask][pos] = ans;

int main() {

cin >> N;

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

cin >> dist[i][j];

memset(dp, -1, sizeof(dp));

cout << tsp(1, 0);

Done😊