Question 1:

Problem Statement: Given two integers N and K, find the number of

ways to distribute K identical candies into N distinct boxes such that
no box contains more than M candies. Print the result modulo
10^9+7.
Input:
 The first line contains three integers N, K, and M.
Output:
 Print a single integer, the number of ways to distribute the
candies.
Constraints:
 1≤N,K,M≤1031 \leq N, K, M \leq 10^3
Sample Input:
352
Sample Output:
6
Solution in C++:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
int N, K, M;
cin >> N >> K >> M;
 vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
dp[0][0] = 1;

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

for (int j = 0; j <= K; j++) {
for (int x = 0; x <= min(M, j); x++) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
}
}
}

cout << dp[N][K] << endl;

return 0;
}

Question 2:
Problem Statement: Find the smallest positive integer X such that
the sum of digits of X equals a given number S.
Input:
 The first line contains a single integer S.
Output:
 Print the smallest integer X or -1 if no such X exists.
Constraints:
 1≤S≤10001 \leq S \leq 1000
Sample Input:
10
Sample Output:
19
Solution in C++:
#include <bits/stdc++.h>
using namespace std;

int main() {
int S;
cin >> S;

if (S > 900) {
cout << -1 << endl;
return 0;
}

string result = "";

while (S > 0) {
int digit = min(S, 9);
result += to_string(digit);
S -= digit;
}
 reverse(result.begin(), result.end());
cout << result << endl;

return 0;
}

Question 3:
Problem Statement: You are given an array of integers A of size N.
Find the maximum sum of a subarray where the sum of the subarray
is divisible by M.
Input:
 The first line contains two integers N and M.
 The second line contains N integers representing the array A.
Output:
 Print the maximum sum of the subarray.
Constraints:
 1≤N≤1051 \leq N \leq 10^5
 1≤M≤1091 \leq M \leq 10^9
 −106≤A[i]≤106-10^6 \leq A[i] \leq 10^6
Sample Input:
53
12345
Sample Output:
12
Solution in C++:
#include <bits/stdc++.h>
using namespace std;

int main() {
int N, M;
cin >> N >> M;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];

vector<int> prefix(N + 1, 0);

for (int i = 1; i <= N; i++) {
prefix[i] = prefix[i - 1] + A[i - 1];
}

int maxSum = 0;
map<int, int> modIndex;

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

int mod = prefix[i] % M;
if (mod < 0) mod += M;

if (modIndex.count(mod)) {
maxSum = max(maxSum, prefix[i] - prefix[modIndex[mod]]);
 } else {
modIndex[mod] = i;
}
}

cout << maxSum << endl;

return 0;
}
4. Matrix Spiral Traversal
Write a program to perform spiral traversal of a given N x M
matrix. Print the elements in the spiral order starting from the
top-left corner.
 Input:
o First line: Two integers, N (rows) and M (columns).
o Next N lines: Space-separated integers representing the
matrix elements.
 Output:
o A single line of space-separated integers in spiral order.
 Constraints:
o 1≤N,M≤1001 \leq N, M \leq 100
o Matrix elements are integers between −105-10^5 and
10510^5.
Solution
#include <iostream>
#include <vector>
using namespace std;

void spiralTraversal(vector<vector<int>> &matrix, int N, int M) {

int top = 0, bottom = N - 1, left = 0, right = M - 1;
vector<int> result;

while (top <= bottom && left <= right) {

for (int i = left; i <= right; ++i) result.push_back(matrix[top][i]);
top++;
for (int i = top; i <= bottom; ++i)
result.push_back(matrix[i][right]);
right--;
if (top <= bottom) {
for (int i = right; i >= left; --i)
result.push_back(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; --i)
result.push_back(matrix[i][left]);
left++;
}
}
for (int x : result) cout << x << " ";
}
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> matrix(N, vector<int>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> matrix[i][j];
spiralTraversal(matrix, N, M);
return 0;
}

5. String Anagram Distance

Given two strings, determine the minimum number of
character deletions required to make them anagrams of each
other.
 Input:
o First line: Two strings, S1 and S2.
 Output:
o Single integer: Minimum number of deletions.
 Constraints:
o 1≤length of S1,S2≤1051 \leq \text{length of } S1, S2 \leq
10^5
o Strings contain lowercase English letters only.
 Solution:
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int minDeletionsToAnagram(string S1, string S2) {

vector<int> freq(26, 0);
for (char c : S1) freq[c - 'a']++;
for (char c : S2) freq[c - 'a']--;
int deletions = 0;
for (int count : freq) deletions += abs(count);
return deletions;
}

int main() {
string S1, S2;
cin >> S1 >> S2;
cout << minDeletionsToAnagram(S1, S2);
return 0;
}
6. Subset Sum Problem
Given an array of integers, determine if there exists a subset
whose sum equals a given target value K.
 Input:
o First line: Two integers, N (size of the array) and K (target
sum).
o Second line: Space-separated integers representing the
array elements.
 Output:
o Print "YES" if such a subset exists, otherwise print "NO".
 Constraints:
o 1≤N≤10001 \leq N \leq 1000
o −104≤array elements≤104-10^4 \leq \text{array elements}
\leq 10^4
o −105≤K≤105-10^5 \leq K \leq 10^5.
 Solution:
#include <iostream>
#include <vector>
using namespace std;

bool subsetSum(vector<int> &arr, int N, int K) {

vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false));
for (int i = 0; i <= N; i++) dp[i][0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
 dp[i][j] = dp[i - 1][j];
if (j >= arr[i - 1]) dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
}
}
return dp[N][K];
}

int main() {
int N, K;
cin >> N >> K;
vector<int> arr(N);
for (int i = 0; i < N; i++) cin >> arr[i];
cout << (subsetSum(arr, N, K) ? "YES" : "NO");
return 0;
}

7. Knight's Tour Problem

Find if it is possible for a knight to visit all cells of an N x N
chessboard exactly once, starting from the top-left corner.
 Input:
o Single integer NN (size of the chessboard).
 Output:
o Print "YES" if such a tour is possible, otherwise print "NO".
 Constraints:
 o 1≤N≤81 \leq N \leq 8.
 Solution:
#include <iostream>
#include <vector>
using namespace std;

bool isSafe(int x, int y, vector<vector<int>> &board, int N) {

return (x >= 0 && y >= 0 && x < N && y < N && board[x][y] ==
-1);
}

bool knightTourUtil(int x, int y, int move, vector<vector<int>>

&board, int N, vector<int> &dx, vector<int> &dy) {
if (move == N * N) return true;
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (isSafe(nx, ny, board, N)) {
board[nx][ny] = move;
if (knightTourUtil(nx, ny, move + 1, board, N, dx, dy))
return true;
board[nx][ny] = -1;
}
}
return false;
}
 bool knightTour(int N) {
vector<vector<int>> board(N, vector<int>(N, -1));
vector<int> dx = {2, 1, -1, -2, -2, -1, 1, 2};
vector<int> dy = {1, 2, 2, 1, -1, -2, -2, -1};
board[0][0] = 0;
return knightTourUtil(0, 0, 1, board, N, dx, dy);
}

int main() {
int N;
cin >> N;
cout << (knightTour(N) ? "YES" : "NO");
return 0;
}

8. Maximum Subarray Product

Find the maximum product that can be achieved by any
contiguous subarray of a given array.
 Input:
o First line: Single integer, N (size of the array).
o Second line: Space-separated integers representing the
array.
 Output:
 o Single integer: Maximum product of any contiguous
subarray.
 Constraints:
o 1≤N≤1051 \leq N \leq 10^5
o −10≤array elements≤10-10 \leq \text{array elements} \leq
10.
 Solution:
#include <iostream>
#include <vector>
using namespace std;

int maxSubarrayProduct(vector<int> &arr, int N) {

int maxProd = arr[0], minProd = arr[0], result = arr[0];
for (int i = 1; i < N; i++) {
if (arr[i] < 0) swap(maxProd, minProd);
maxProd = max(arr[i], maxProd * arr[i]);
minProd = min(arr[i], minProd * arr[i]);
result = max(result, maxProd);
}
return result;
}

int main() {
int N;
 cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) cin >> arr[i];
cout << maxSubarrayProduct(arr, N);
return 0;
}

Question 9
Problem Statement:
You are given two integers X and Y. Find the minimum number
of operations required to convert X into Y. The following
operations are allowed:
1. If X is even, divide it by 2.
2. Add 1 to X.
3. Subtract 1 from X.
Input:
 The first line contains two integers X and Y.
Output:
 Output a single integer representing the minimum number of
operations.
Constraints:
 1≤X,Y≤1061 \leq X, Y \leq 10^6
Example Input:
83
Example Output:
5
Solution in C++:
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

int minOperations(int X, int Y) {

queue<pair<int, int>> q;
unordered_set<int> visited;

q.push({X, 0});
visited.insert(X);

while (!q.empty()) {
int curr = q.front().first;
int steps = q.front().second;
q.pop();

if (curr == Y)
return steps;

if (curr > 0 && visited.find(curr - 1) == visited.end()) {

q.push({curr - 1, steps + 1});
 visited.insert(curr - 1);
}
if (visited.find(curr + 1) == visited.end()) {
q.push({curr + 1, steps + 1});
visited.insert(curr + 1);
}
if (curr % 2 == 0 && visited.find(curr / 2) == visited.end()) {
q.push({curr / 2, steps + 1});
visited.insert(curr / 2);
}
}
return -1;
}

int main() {
int X, Y;
cin >> X >> Y;
cout << minOperations(X, Y) << endl;
return 0;
}

Question 10
Problem Statement:
You are given an integer N. Your task is to generate a matrix of
size N×NN \times N such that:
1. Each row contains integers from 1 to NN in ascending order.
2. Every even row is reversed.
Input:
 A single integer N.
Output:
 Print the generated matrix.
Constraints:
 1≤N≤1031 \leq N \leq 10^3
Example Input:
3
Example Output:
123
654
789
Solution in C++:
#include <iostream>
using namespace std;

void generateMatrix(int N) {
int num = 1;
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
for (int j = 0; j < N; j++) {
cout << num++ << " ";
 }
} else {
int temp = num + N - 1;
for (int j = 0; j < N; j++) {
cout << temp-- << " ";
num++;
}
}
cout << endl;
}
}

int main() {
int N;
cin >> N;
generateMatrix(N);
return 0;
}

Question 11
Problem Statement:
You are given an integer N. Find all pairs of integers (a,b)(a, b)
such that:
1. 1≤a,b≤N1 \leq a, b \leq N
2. a2+b2a^2 + b^2 is a perfect square.
 Input:
 A single integer N.
Output:
 Print all pairs (a,b)(a, b) in ascending order of a and then b.
Constraints:
 1≤N≤10001 \leq N \leq 1000
Example Input:
5
Example Output:
34
43
Solution in C++:
#include <iostream>
#include <cmath>
using namespace std;

void findPairs(int N) {
for (int a = 1; a <= N; a++) {
for (int b = 1; b <= N; b++) {
int sum = a * a + b * b;
int root = sqrt(sum);
if (root * root == sum) {
cout << a << " " << b << endl;
}
 }
}
}

int main() {
int N;
cin >> N;
findPairs(N);
return 0;
}

Question 12
Problem Statement:
You are given two integers N and M. Find the number of ways
to fill a N×MN \times M grid using 2x1 dominoes such that no
dominoes overlap or go outside the grid.
Input:
 Two integers N and M.
Output:
 Output a single integer representing the number of ways to fill
the grid modulo 109+710^9 + 7.
Constraints:
 1≤N,M≤1031 \leq N, M \leq 10^3
Example Input:
23
Example Output:
3
Solution in C++:
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

int countWays(int N, int M) {

vector<int> dp(M + 1, 0);
dp[0] = 1;

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

dp[i] = dp[i - 1];
if (i >= 2) dp[i] = (dp[i] + dp[i - 2]) % MOD;
}

return dp[M];
}

int main() {
int N, M;
cin >> N >> M;
if (N % 2 != 0) cout << 0 << endl;
 else cout << countWays(N, M) << endl;
return 0;
}
Question 13
Problem Statement:
You are given an integer array nums and an integer target. Your
task is to find a subarray whose sum is closest to the given
target. If there are multiple subarrays with the same closest
sum, return the one with the smallest length.
Input:
The first line contains an integer n, the size of the array.
The second line contains n integers representing the array.
The third line contains an integer target.
Output:
Output the closest sum to the target and the length of the
subarray.
Constraints:
 1≤n≤1051 \leq n \leq 10^5
 −104≤nums[i]≤104-10^4 \leq nums[i] \leq 10^4
 −106≤target≤106-10^6 \leq target \leq 10^6
Example Input:
5
2 -3 4 -1 6
5
Example Output:
52
Solution in C++:
#include <bits/stdc++.h>
using namespace std;

int main() {
int n, target;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
cin >> target;

map<int, int> prefixSum;

prefixSum[0] = -1;
int sum = 0, closest = INT_MAX, minLength = INT_MAX,
resultSum = 0;

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

sum += nums[i];
auto it = prefixSum.lower_bound(sum - target);
for (int k = 0; k < 2 && it != prefixSum.end(); k++, it++) {
int currentSum = sum - it->first;
int length = i - it->second;
if (abs(currentSum - target) < abs(closest - target) ||
 (abs(currentSum - target) == abs(closest - target) &&
length < minLength)) {
closest = currentSum;
minLength = length;
resultSum = sum - it->first;
}
}
prefixSum[sum] = i;
}

cout << resultSum << " " << minLength << endl;
return 0;
}

Question 14
Problem Statement:
Given an integer n, determine the number of distinct prime
factorizations of all numbers from 1 to n modulo 109+710^9+7.
Input:
The first line contains an integer n.
Output:
Print the result modulo 109+710^9+7.
Constraints:
 1≤n≤1061 \leq n \leq 10^6
Example Input:
5
Example Output:
5

Solution in C++:
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
int n;
cin >> n;
vector<int> sieve(n + 1, 1);
vector<int> primeCount(n + 1, 0);

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

if (sieve[i] == 1) {
for (int j = i; j <= n; j += i) {
sieve[j] = 0;
primeCount[j]++;
}
}
}
 int result = 0;
for (int i = 1; i <= n; i++) {
result = (result + primeCount[i]) % MOD;
}

cout << result << endl;

return 0;
}

Question 15
Problem Statement:
You are given a string s containing only lowercase English
letters. Find the lexicographically smallest string that can be
obtained by removing exactly one character.
Input:
The first line contains a string s.
Output:
Print the lexicographically smallest string.
Constraints:
 1≤∣s∣≤1051 \leq |s| \leq 10^5
Example Input:
abcde
Example Output:
abde
Solution in C++:
#include <bits/stdc++.h>
using namespace std;

int main() {
string s;
cin >> s;

int n = s.size();
for (int i = 0; i < n - 1; i++) {
if (s[i] > s[i + 1]) {
s.erase(i, 1);
cout << s << endl;
return 0;
}
}

s.pop_back();
cout << s << endl;
return 0;
}
Question 16
Problem Statement:
Given a 2D grid of size N x M, find the maximum sum of any path
starting from the top-left corner (1,1) to the bottom-right corner
(N,M). You can only move right or down.
Input:
 First line contains two integers N and M, the dimensions of the
grid.
 Next N lines contain M integers each, representing the grid.
Output:
 Single integer, the maximum sum.
Constraints:
1 ≤ N, M ≤ 1000
-10^6 ≤ Grid[i][j] ≤ 10^6
Example Input:
33
123
456
789
Example Output:
29
C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
vector<vector<int>> dp(n, vector<int>(m, 0));

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

for (int j = 0; j < m; j++)
cin >> grid[i][j];

dp[0][0] = grid[0][0];
for (int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < m; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

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

for (int j = 1; j < m; j++)
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];

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

return 0;
}

Question 17
Problem Statement:
Find the number of pairs (i, j) such that 1 ≤ i < j ≤ N and A[i] + A[j] is
divisible by K.
Input:
 First line contains two integers N and K.
 Second line contains N integers A[i].
Output:
 Single integer, the count of such pairs.
Constraints:
1 ≤ N ≤ 100000
1 ≤ K ≤ 1000
1 ≤ A[i] ≤ 10^9
Example Input:
53
12345
Example Output:
4
C++ Solution:
#include <bits/stdc++.h>
using namespace std;

int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
 vector<int> freq(k, 0);

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

cin >> a[i];
freq[a[i] % k]++;
}

int count = freq[0] * (freq[0] - 1) / 2;

for (int i = 1; i <= k / 2; i++) {
if (i != k - i)
count += freq[i] * freq[k - i];
else
count += freq[i] * (freq[i] - 1) / 2;
}

cout << count;

return 0;
}

Question 17
Problem Statement:
A farmer is growing an orchard with N trees. The farmer needs to
divide the trees into K groups such that each group has at least one
tree, and the product of the number of trees in all groups is
maximized.
Input:
 First line contains integers N and K.
Constraints:
 1≤N,K≤1031 \leq N, K \leq 10^3.
Output:
 Print the maximum product modulo 109+710^9 + 7.
Sample Input
10 3
Sample Output
36
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
int N, K;
cin >> N >> K;

vector<int> groups(K, N / K);

for (int i = 0; i < N % K; i++) groups[i]++;

long long result = 1;

for (int x : groups) result = (result * x) % MOD;
 cout << result << endl;
return 0;
}

Question 18
Problem Statement:
You have a list of N integers. Find the minimum cost to make all
elements in the list equal by either incrementing or decrementing a
number by 1.
Input:
 First line contains integer N.
 Second line contains N integers A[i]A[i].
Constraints:
 1≤N≤1051 \leq N \leq 10^5
 1≤A[i]≤1091 \leq A[i] \leq 10^9.
Output:
 Print the minimum cost.
Sample Input
4
1 2 9 10
Sample Output
16
Solution (C++)
#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];

sort(A.begin(), A.end());
int median = A[N / 2];
long long cost = 0;

for (int x : A) cost += abs(x - median);

cout << cost << endl;
return 0;
}

Question 19
Problem Statement:
Given an array of integers, find the number of distinct pairs (i,j)(i, j)
such that A[i]+A[j]A[i] + A[j] is divisible by K.
Input:
 First line contains integers N and K.
 Second line contains N integers A[i]A[i].
Constraints:
  1≤N≤1051 \leq N \leq 10^5
 1≤K≤1051 \leq K \leq 10^5
 1≤A[i]≤1091 \leq A[i] \leq 10^9.
Output:
 Print the count of such pairs.
Sample Input
53
12345
Sample Output
4
Solution (C++)
#include<bits/stdc++.h>
using namespace std;

int main() {
int N, K;
cin >> N >> K;

vector<int> freq(K, 0);

int num;

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

cin >> num;
freq[num % K]++;
 }

long long count = (long long)freq[0] * (freq[0] - 1) / 2;

for (int i = 1; i <= K / 2; i++) {

if (i == K - i) count += (long long)freq[i] * (freq[i] - 1) / 2;
else count += (long long)freq[i] * freq[K - i];
}

cout << count << endl;

return 0;
}

Question 20
Problem Statement:
Find the total number of subarrays having an XOR equal to K.
Input:
 First line contains integers N and K.
 Second line contains NN integers A[i]A[i].
Constraints:
 1≤N≤1051 \leq N \leq 10^5, 0≤K≤1090 \leq K \leq 10^9,
0≤A[i]≤1090 \leq A[i] \leq 10^9.
Output:
 Print the total count of subarrays.
Sample Input
54
42264
Sample Output
4
Solution (C++)
#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];

unordered_map<int, int> freq;

int XOR = 0, count = 0;

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

XOR ^= A[i];
if (XOR == K) count++;
if (freq.find(XOR ^ K) != freq.end()) count += freq[XOR ^ K];
freq[XOR]++;
}
 cout << count << endl;
return 0;
}
Question 21
Problem Statement:
Given a grid of size N x M with each cell having a cost, find the
minimum cost to traverse from the top-left corner to the bottom-
right corner. You can move only right or down.
Input:
 First line contains integers N and M.
 Next N lines contain M integers representing the grid.
Constraints:
 1≤N,M≤5001 \leq N, M \leq 500
 1≤grid[i][j]≤1031 \leq \text{grid}[i][j] \leq 10^3.
Output:
 Print the minimum cost.
Sample Input
33
131
151
421
Sample Output
7
Solution (C++)
#include<bits/stdc++.h>
using namespace std;

int main() {
int N, M;
cin >> N >> M;

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

for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> grid[i][j];

vector<vector<int>> dp(N, vector<int>(M, INT_MAX));

dp[0][0] = grid[0][0];

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

for (int j = 0; j < M; j++) {
if (i > 0) dp[i][j] = min(dp[i][j], dp[i-1][j] + grid[i][j]);
if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j-1] + grid[i][j]);
}
}

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

return 0;
}

Question 22
Problem Statement:
You are given a string S of length N. Find the longest palindromic
substring in S.
Input:
 First line contains string S.
Constraints:
 1≤N≤1031 \leq N \leq 10^3.
Output:
 Print the longest palindromic substring.
Sample Input
babad
Sample Output
bab
Solution (C++)
#include<bits/stdc++.h>
using namespace std;

string longestPalindrome(string S) {
int N = S.size(), start = 0, maxLength = 1;
vector<vector<bool>> dp(N, vector<bool>(N, false));

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

 for (int length = 2; length <= N; length++) {
for (int i = 0; i <= N - length; i++) {
int j = i + length - 1;
if (S[i] == S[j] && (length == 2 || dp[i+1][j-1])) {
dp[i][j] = true;
if (length > maxLength) {
maxLength = length;
start = i;
}
}
}
}
return S.substr(start, maxLength);
}

int main() {
string S;
cin >> S;
cout << longestPalindrome(S) << endl;
return 0;
}
Question 23
Problem Statement:
Given a tree with N nodes, each having a value, find the maximum
sum of values in a path from any node to any other node.
Input:
 First line contains N.
 Second line contains N integers (values of nodes).
 Next N−1N-1 lines contain edges between nodes.
Constraints:
 2≤N≤1052 \leq N \leq 10^5, values can be negative or positive.
Output:
 Print the maximum sum path.
Sample Input
5
1 2 3 -2 -1
12
13
34
35
Sample Output
6
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<int> values;
int maxSum = INT_MIN;

int dfs(int node, int parent) {

int maxPath = values[node - 1], maxSingle = values[node - 1];
for (int neighbor : tree[node]) {
if (neighbor == parent) continue;
int childSum = dfs(neighbor, node);
maxSingle = max(maxSingle, values[node - 1] + childSum);
}
maxSum = max(maxSum, maxSingle);
return max(maxPath, maxSingle);
}

int main() {
int N;
cin >> N;
values.resize(N);
tree.resize(N + 1);

for (int i = 0; i < N; i++) cin >> values[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, -1);
cout << maxSum << endl;
return 0;
}
Question 24
Problem Statement:
Given an array of integers, find the number of subarrays whose sum
is divisible by k.
Input:
 First line contains integers N (length of array) and k.
 Second line contains N integers representing the array.
Constraints:
 1≤N≤1051 \leq N \leq 10^5
 1≤k≤1031 \leq k \leq 10^3
 −109≤array[i]≤109-10^9 \leq \text{array[i]} \leq 10^9
Output:
 Print the count of subarrays whose sum is divisible by k.
Sample Input
45
1234
Sample Output
2
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
int N, k;
cin >> N >> k;
vector<int> arr(N);
for (int i = 0; i < N; i++) cin >> arr[i];

unordered_map<int, int> prefixSumMod;

prefixSumMod[0] = 1;
int sum = 0, count = 0;

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

sum += arr[i];
int mod = sum % k;
if (mod < 0) mod += k;
count += prefixSumMod[mod];
prefixSumMod[mod]++;
}
 cout << count << endl;
return 0;
}

Question 25
Problem Statement:
Given an integer n, find the number of ways to partition n into the
sum of one or more positive integers. Two partitions that differ only
in the order of their summands are considered the same.
Input:
 First line contains the integer n.
Constraints:
 1≤n≤10001 \leq n \leq 1000
Output:
 Print the number of distinct partitions of n.
Sample Input
5
Sample Output
7
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
 cin >> n;
vector<int> dp(n + 1, 0);
dp[0] = 1;

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

for (int j = i; j <= n; j++) {
dp[j] += dp[j - i];
}
}

cout << dp[n] << endl;

return 0;
}

Question 26
Problem Statement:
You are given a sequence of integers, and you need to find the
longest increasing subsequence (LIS) in the sequence.
Input:
 First line contains the integer n (size of the sequence).
 Second line contains the sequence of n integers.
Constraints:
 1≤n≤1051 \leq n \leq 10^5
 1≤arr[i]≤1091 \leq \text{arr}[i] \leq 10^9
Output:
  Print the length of the longest increasing subsequence.
Sample Input
6
10 9 2 5 3 7
Sample Output
3
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];

vector<int> lis;
for (int i = 0; i < n; i++) {
auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
if (it == lis.end()) lis.push_back(arr[i]);
else *it = arr[i];
}

cout << lis.size() << endl;

 return 0;
}

Question 27
Problem Statement:
You are given a matrix N x N representing a maze, where 1 represents
an open path and 0 represents a wall. Find the shortest path from
the top-left corner to the bottom-right corner, moving only through
open paths (1).
Input:
 First line contains integer N.
 Next N lines contain N integers representing the maze.
Constraints:
 1≤N≤10001 \leq N \leq 1000
Output:
 Print the length of the shortest path. If no path exists, print -1.
Sample Input
4
1010
1110
0101
1111
Sample Output
7
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int dx[] = {1, 0, -1, 0};

int dy[] = {0, 1, 0, -1};

bool isValid(int x, int y, int N, vector<vector<int>>& maze) {

return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

int bfs(int N, vector<vector<int>>& maze) {

queue<pair<int, int>> q;
vector<vector<int>> dist(N, vector<int>(N, -1));

dist[0][0] = 0;
q.push({0, 0});

while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();

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

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

 int nx = x + dx[i], ny = y + dy[i];
if (isValid(nx, ny, N, maze) && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}

return -1;
}

int main() {
int N;
cin >> N;
vector<vector<int>> maze(N, vector<int>(N));

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

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

cout << bfs(N, maze) << endl;

return 0;
}
Question 28
Problem Statement:
Given a list of jobs with start time, finish time, and profit, find the
maximum profit you can earn by scheduling jobs such that no two
jobs overlap.
Input:
 First line contains the integer N (number of jobs).
 Next N lines contain three integers: start time, finish time, and
profit of the job.
Constraints:
 1≤N≤10001 \leq N \leq 1000
 1≤start time,finish time≤1051 \leq \text{start time}, \text{finish
time} \leq 10^5
 0≤profit≤1050 \leq \text{profit} \leq 10^5
Output:
 Print the maximum profit you can earn.
Sample Input
4
1 3 50
2 5 20
4 6 70
6 8 60
Sample Output
150
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

bool compareJobs(pair<int, pair<int, int>>& a, pair<int, pair<int,

int>>& b) {
return a.second.first < b.second.first;
}

int findLastNonConflicting(vector<pair<int, pair<int, int>>>& jobs, int

i) {
for (int j = i - 1; j >= 0; j--) {
if (jobs[j].second.first <= jobs[i].second.first)
return j;
}
return -1;
}

int main() {
int N;
cin >> N;
vector<pair<int, pair<int, int>>> jobs(N);

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

cin >> jobs[i].second.first >> jobs[i].second.second >> jobs[i].first;
 sort(jobs.begin(), jobs.end(), compareJobs);

vector<int> dp(N);
dp[0] = jobs[0].first;

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

int includeProfit = jobs[i].first;
int l = findLastNonConflicting(jobs, i);
if (l != -1) includeProfit += dp[l];

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

}

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

return 0;
}

Question 29
Problem Statement:
Given a string, find the length of the longest substring without
repeating characters.
Input:
 A single string s.
Constraints:
  1≤len(s)≤1051 \leq \text{len(s)} \leq 10^5
Output:
 Print the length of the longest substring without repeating
characters.
Sample Input
abcabcbb
Sample Output
3
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map;
int start = 0, maxLength = 0;

for (int end = 0; end < s.length(); end++) {

if (map.find(s[end]) != map.end()) {
start = max(start, map[s[end]] + 1);
}
map[s[end]] = end;
maxLength = max(maxLength, end - start + 1);
}
return maxLength;
}

int main() {
string s;
cin >> s;
cout << lengthOfLongestSubstring(s) << endl;
return 0;
}

Question 30
Problem Statement:
Given an integer n, print all the prime numbers up to n.
Input:
 A single integer n.
Constraints:
 1≤n≤1061 \leq n \leq 10^6
Output:
 Print all prime numbers from 1 to n.
Sample Input
10
Sample Output
2357
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

void sieveOfEratosthenes(int n) {
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;

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

if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}

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

if (prime[i]) cout << i << " ";
}
}

int main() {
int n;
cin >> n;
sieveOfEratosthenes(n);
return 0;
}

Question 31
Problem Statement:
You are given a list of integers. Find the maximum sum of a subarray
of length k.
Input:
 First line contains integers n and k.
 Second line contains the array of n integers.
Constraints:
 1≤n≤1051 \leq n \leq 10^5
 1≤k≤n1 \leq k \leq n
 −105≤array[i]≤105-10^5 \leq \text{array[i]} \leq 10^5
Output:
 Print the maximum sum of a subarray of length k.
Sample Input
53
21513
Sample Output
9
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
 int n, k;
cin >> n >> k;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];

int windowSum = 0, maxSum = INT_MIN;

for (int i = 0; i < k; i++) windowSum += arr[i];

maxSum = windowSum;

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

windowSum += arr[i] - arr[i - k];
maxSum = max(maxSum, windowSum);
}

cout << maxSum << endl;

return 0;
}

Question 32
Problem Statement:
You are given a list of integers, and you need to find the largest
product of three numbers in the list.
Input:
 A single line containing n integers, the list of numbers.
Constraints:
 3≤n≤10003 \leq n \leq 1000
 −103≤array[i]≤103-10^3 \leq \text{array[i]} \leq 10^3
Output:
 Print the largest product of any three numbers in the list.
Sample Input
-10 -10 5 2
Sample Output
500
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];

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

int product1 = arr[0] * arr[1] * arr[n - 1]; // Two negative numbers

and one positive
 int product2 = arr[n - 1] * arr[n - 2] * arr[n - 3]; // Three largest
positive numbers

cout << max(product1, product2) << endl;

return 0;
}

Question 33
Problem Statement:
Given an array of integers, find the majority element (the element
that appears more than n / 2 times). If no such element exists, return
-1.
Input:
 The first line contains integer n.
 The second line contains n integers representing the array.
Constraints:
 1≤n≤1051 \leq n \leq 10^5
 −109≤array[i]≤109-10^9 \leq \text{array[i]} \leq 10^9
Output:
 Print the majority element, or -1 if no majority element exists.
Sample Input
5
33424
Sample Output
-1
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int majorityElement(vector<int>& nums) {

int count = 0, candidate = -1;

for (int num : nums) {

if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}

count = 0;
for (int num : nums) {
if (num == candidate) count++;
}

return (count > nums.size() / 2) ? candidate : -1;

}

int main() {
int n;
 cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];

cout << majorityElement(arr) << endl;

return 0;
}

Question 34
Problem Statement:
You are given an integer n. Find the number of trailing zeros in the
factorial of n.
Input:
 A single integer n.
Constraints:
 1≤n≤1051 \leq n \leq 10^5
Output:
 Print the number of trailing zeros in n!.
Sample Input
5
Sample Output
1
Solution (C++)
#include <bits/stdc++.h>
using namespace std;
int trailingZeroes(int n) {
int count = 0;
while (n >= 5) {
n /= 5;
count += n;
}
return count;
}

int main() {
int n;
cin >> n;
cout << trailingZeroes(n) << endl;
return 0;
}

Question 35
Problem Statement:
Given a matrix of integers, find the number of distinct paths from the
top-left corner to the bottom-right corner. You can only move right or
down at any point in time.
Input:
 First line contains two integers m and n, representing the
dimensions of the matrix.
  The second line contains a matrix of size m x n.
Constraints:
 1≤m,n≤1001 \leq m, n \leq 100
Output:
 Print the number of distinct paths from top-left to bottom-right
corner.
Sample Input
33
000
000
000
Sample Output
6
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int uniquePaths(int m, int n) {

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

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

for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
 }

return dp[m - 1][n - 1];

}

int main() {
int m, n;
cin >> m >> n;
cout << uniquePaths(m, n) << endl;
return 0;
}

Question 36
Problem Statement:
Find the length of the longest palindromic subsequence in a given
string.
Input:
 A single string s.
Constraints:
 1≤len(s)≤10001 \leq \text{len(s)} \leq 1000
Output:
 Print the length of the longest palindromic subsequence.
Sample Input
bbabcbab
Sample Output
7
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int longestPalindromicSubseq(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));

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

for (int length = 2; length <= n; length++) {

for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
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 << longestPalindromicSubseq(s) << endl;
return 0;
}

Question 37
Problem Statement:
Given a sorted array, remove the duplicates in-place such that each
element appears only once and return the new length of the array.
Input:
 A sorted array of integers.
Constraints:
 1≤n≤1041 \leq n \leq 10^4
Output:
 Print the length of the array after removing duplicates.
Sample Input
112
Sample Output
2
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int removeDuplicates(vector<int>& nums) {

if (nums.empty()) return 0;
 int j = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[j]) {
j++;
nums[j] = nums[i];
}
}

return j + 1;
}

int main() {
vector<int> nums;
int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
nums.push_back(temp);
}

cout << removeDuplicates(nums) << endl;

return 0;
}
Question 38
Problem Statement:
Find the first non-repeating character in a string. If it doesn't exist,
return -1.
Input:
 A single string s.
Constraints:
 1≤len(s)≤1051 \leq \text{len(s)} \leq 10^5
Output:
 Print the first non-repeating character or -1 if none exists.
Sample Input
leetcode
Sample Output
l
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

char firstUniqChar(string s) {
unordered_map<char, int> count;

for (char c : s) {
count[c]++;
}
 for (char c : s) {
if (count[c] == 1) return c;
}

return '-1';
}

int main() {
string s;
cin >> s;
cout << firstUniqChar(s) << endl;
return 0;
}

Question 39
Problem Statement:
Find the minimum number of moves to reach the target number
from 1. In each move, you can multiply the current number by 2 or 3,
or subtract 1 from it.
Input:
 A single integer target.
Constraints:
 1≤target≤1051 \leq \text{target} \leq 10^5
Output:
  Print the minimum number of moves to reach the target from
1.
Sample Input
10
Sample Output
4
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int minMoves(int target) {

queue<pair<int, int>> q;
q.push({1, 0});
unordered_set<int> visited;
visited.insert(1);

while (!q.empty()) {
int num = q.front().first;
int steps = q.front().second;
q.pop();

if (num == target) return steps;

if (num * 2 <= target && visited.find(num * 2) == visited.end()) {

 q.push({num * 2, steps + 1});
visited.insert(num * 2);
}

if (num * 3 <= target && visited.find(num * 3) == visited.end()) {

q.push({num * 3, steps + 1});
visited.insert(num * 3);
}

if (num - 1 > 0 && visited.find(num - 1) == visited.end()) {

q.push({num - 1, steps + 1});
visited.insert(num - 1);
}
}

return -1;
}

int main() {
int target;
cin >> target;
cout << minMoves(target) << endl;
return 0;
}
Question 40
Problem Statement:
Find the maximum area of a rectangle in a histogram.
Input:
 The first line contains the integer n, the number of bars.
 The second line contains the heights of the bars.
Constraints:
 1≤n≤1051 \leq n \leq 10^5
 1≤height[i]≤1031 \leq \text{height[i]} \leq 10^3
Output:
 Print the maximum area of the rectangle.
Sample Input
5
21562
Sample Output
10
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int maxArea(vector<int>& heights) {

stack<int> s;
int maxArea = 0, i = 0;
 while (i < heights.size()) {
if (s.empty() || heights[i] >= heights[s.top()]) {
s.push(i++);
} else {
int h = heights[s.top()];
s.pop();
int width = s.empty() ? i : i - s.top() - 1;
maxArea = max(maxArea, h * width);
}
}

while (!s.empty()) {
int h = heights[s.top()];
s.pop();
int width = s.empty() ? i : i - s.top() - 1;
maxArea = max(maxArea, h * width);
}

return maxArea;
}

int main() {
int n;
 cin >> n;
vector<int> heights(n);
for (int i = 0; i < n; i++) cin >> heights[i];

cout << maxArea(heights) << endl;

return 0;
}

Question 41
Problem Statement:
Given a string s, return the number of distinct subsequences of s
which are palindromes.
Input:
 A single string s.
Constraints:
 1≤len(s)≤10001 \leq \text{len(s)} \leq 1000
Output:
 Print the number of distinct palindromic subsequences.
Sample Input
aab
Sample Output
4
Solution (C++)
#include <bits/stdc++.h>
using namespace std;
int countPalindromicSubsequences(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));

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

for (int length = 2; length <= n; length++) {

for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
else dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
}

return dp[0][n - 1];

}

int main() {
string s;
cin >> s;
cout << countPalindromicSubsequences(s) << endl;
return 0;
}
Question 42
Problem Statement:
Given an array of integers, find the maximum product of any two
integers.
Input:
 A single array of integers nums.
Constraints:
 2≤len(nums)≤1042 \leq \text{len(nums)} \leq 10^4
 −103≤nums[i]≤103-10^3 \leq \text{nums[i]} \leq 10^3
Output:
 Print the maximum product of any two integers.
Sample Input
31456
Sample Output
30
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int maxProduct(vector<int>& nums) {

int max1 = INT_MIN, max2 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;

for (int num : nums) {

 if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}

if (num < min1) {

min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}

return max(max1 * max2, min1 * min2);

}

int main() {
vector<int> nums;
int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
 nums.push_back(temp);
}

cout << maxProduct(nums) << endl;

return 0;
}

Question 43
Problem Statement:
Given a number n, find the smallest number whose sum of digits
equals n and it has the minimum possible number of digits.
Input:
 A single integer n.
Constraints:
 1≤n≤10001 \leq n \leq 1000
Output:
 Print the smallest number whose sum of digits equals n.
Sample Input
9
Sample Output
9
Solution (C++)
#include <bits/stdc++.h>
using namespace std;
int smallestNumber(int n) {
string result = "";
while (n > 9) {
result += '9';
n -= 9;
}
if (n > 0) result += to_string(n);
reverse(result.begin(), result.end());
return stoi(result);
}

int main() {
int n;
cin >> n;
cout << smallestNumber(n) << endl;
return 0;
}

Question 44
Problem Statement:
Find the maximum subarray sum in an array of integers.
Input:
 A single array of integers nums.
Constraints:
  1≤len(nums)≤1041 \leq \text{len(nums)} \leq 10^4
 −103≤nums[i]≤103-10^3 \leq \text{nums[i]} \leq 10^3
Output:
 Print the maximum subarray sum.
Sample Input
-2 1 -3 4 -1 2 1 -5 4
Sample Output
6
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int>& nums) {

int maxSum = nums[0], currentSum = nums[0];

for (int i = 1; i < nums.size(); i++) {

currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}

return maxSum;
}

int main() {
 vector<int> nums;
int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
nums.push_back(temp);
}

cout << maxSubArray(nums) << endl;

return 0;
}

Question 45
Problem Statement:
Given a binary tree, find the maximum depth of the tree.
Input:
 A binary tree represented by a series of integers.
 -1 represents a null node.
Constraints:
 The number of nodes in the tree is at most 10510^5.
Output:
 Print the maximum depth of the tree.
Sample Input
1 2 3 -1 5 -1 -1
Sample Output
3
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxDepth(TreeNode* root) {

if (root == NULL) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

int main() {
// Building the tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
 cout << maxDepth(root) << endl;
return 0;
}

Question 46
Problem Statement:
Find the longest common subsequence (LCS) between two strings.
Input:
 Two strings s1 and s2.
Constraints:
 1≤len(s1),len(s2)≤10001 \leq \text{len(s1)}, \text{len(s2)} \leq
1000
Output:
 Print the length of the longest common subsequence.
Sample Input
abcde
ace
Sample Output
3
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int longestCommonSubsequence(string s1, string s2) {

int m = s1.length(), n = s2.length();
 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

for (int j = 1; j <= n; 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]);
}
}

return dp[m][n];
}

int main() {
string s1, s2;
cin >> s1 >> s2;
cout << longestCommonSubsequence(s1, s2) << endl;
return 0;
}

Question 47
Problem Statement:
Given a string, find all permutations of the string without repeating
characters.
Input:
 A single string s.
Constraints:
 1≤len(s)≤101 \leq \text{len(s)} \leq 10
Output:
 Print all the distinct permutations of the string.
Sample Input
abc
Sample Output
abc
acb
bac
bca
cab
cba
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

void permute(string s, int l, int r, set<string>& result) {

if (l == r) {
result.insert(s);
} else {
for (int i = l; i <= r; i++) {
swap(s[l], s[i]);
permute(s, l + 1, r, result);
 swap(s[l], s[i]);
}
}
}

int main() {
string s;
cin >> s;
set<string> result;
permute(s, 0, s.length() - 1, result);
for (const auto& str : result) {
cout << str << endl;
}
return 0;
}

Question 48
Problem Statement:
Find the intersection of two arrays. Each element in the result must
be unique.
Input:
 Two arrays nums1 and nums2.
Constraints:
 1≤len(nums1),len(nums2)≤10001 \leq \text{len(nums1)},
\text{len(nums2)} \leq 1000
Output:
 Print the intersection of the two arrays.
Sample Input
1221
22
Sample Output
2
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

set<int> set1(nums1.begin(), nums1.end());
set<int> set2(nums2.begin(), nums2.end());
vector<int> result;

for (int num : set1) {

if (set2.find(num) != set2.end()) {
result.push_back(num);
}
}

return result;
}
int main() {
vector<int> nums1 = {1, 2, 2, 1};
vector<int> nums2 = {2, 2};

vector<int> result = intersection(nums1, nums2);

for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
}

Question 49
Problem Statement:
Given an array of integers, return the indices of the two numbers
such that they add up to a specific target.
Input:
 An array nums and an integer target.
Constraints:
 2≤len(nums)≤1042 \leq \text{len(nums)} \leq 10^4
 −103≤nums[i]≤103-10^3 \leq \text{nums[i]} \leq 10^3
 The answer is guaranteed to be unique.
Output:
 Print the indices of the two numbers.
Sample Input
[2, 7, 11, 15]
target = 9
Sample Output
01
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (map.find(complement) != map.end()) {
return {map[complement], i};
}
map[nums[i]] = i;
}
return {};
}

int main() {
vector<int> nums = {2, 7, 11, 15};
int target = 9;
 vector<int> result = twoSum(nums, target);
cout << result[0] << " " << result[1] << endl;
return 0;
}

Question 50
Problem Statement:
Check if a given string is a valid palindrome. Ignore spaces,
punctuation, and capitalization.
Input:
 A single string s.
Constraints:
 1≤len(s)≤1051 \leq \text{len(s)} \leq 10^5
Output:
 Print true if the string is a valid palindrome, otherwise false.
Sample Input
A man, a plan, a canal, Panama
Sample Output
true
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string s) {
 string cleanString = "";
for (char c : s) {
if (isalnum(c)) {
cleanString += tolower(c);
}
}

int left = 0, right = cleanString.length() - 1;

while (left < right) {
if (cleanString[left] != cleanString[right]) {
return false;
}
left++;
right--;
}
return true;
}

int main() {
string s;
getline(cin, s);

cout << (isPalindrome(s) ? "true" : "false") << endl;

return 0;
}

Question 51
Problem Statement:
Given a matrix of integers, find the sum of all elements in the matrix.
Input:
 A matrix m x n.
Constraints:
 1≤m,n≤10001 \leq m, n \leq 1000
 Each integer in the matrix is between −103-10^3 and 10310^3.
Output:
 Print the sum of all the elements in the matrix.
Sample Input
123
456
789
Sample Output
45
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int sumMatrix(vector<vector<int>>& matrix) {

int sum = 0;
 for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
sum += matrix[i][j];
}
}
return sum;
}

int main() {
vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
cout << sumMatrix(matrix) << endl;
return 0;
}

Question 52
Problem Statement:
Given a list of integers, find the first missing positive integer.
Input:
 A list of integers nums.
Constraints:
 1≤len(nums)≤10001 \leq \text{len(nums)} \leq 1000
 −103≤nums[i]≤103-10^3 \leq \text{nums[i]} \leq 10^3
Output:
 Print the smallest missing positive integer.
Sample Input
[1, 2, 0]
Sample Output
3
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int firstMissingPositive(vector<int>& nums) {

int n = nums.size();
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !=
nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}

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

if (nums[i] != i + 1) {
return i + 1;
}
}

return n + 1;
}

int main() {
vector<int> nums = {1, 2, 0};
cout << firstMissingPositive(nums) << endl;
return 0;
}

Question 53
Problem Statement:
Given a string s, return the length of the longest substring without
repeating characters.
Input:
 A string s.
Constraints:
 1≤len(s)≤1041 \leq \text{len(s)} \leq 10^4
Output:
 Print the length of the longest substring without repeating
characters.
Sample Input
abcabcbb
Sample Output
3
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map;
int left = 0, right = 0, maxLength = 0;

while (right < s.length()) {

if (map.find(s[right]) != map.end()) {
left = max(left, map[s[right]] + 1);
}
map[s[right]] = right;
maxLength = max(maxLength, right - left + 1);
right++;
}

return maxLength;
}

int main() {
string s;
cin >> s;

cout << lengthOfLongestSubstring(s) << endl;

return 0;
}

Question 54
Problem Statement:
Given a non-empty array nums of integers, find the maximum
product of any two numbers.
Input:
 An array nums of integers.
Constraints:
 2≤len(nums)≤1042 \leq \text{len(nums)} \leq 10^4
 −103≤nums[i]≤103-10^3 \leq \text{nums[i]} \leq 10^3
Output:
 Print the maximum product of any two numbers.
Sample Input
[1, 2, 3, 4]
Sample Output
12
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int maxProduct(vector<int>& nums) {

sort(nums.begin(), nums.end());
return (nums[nums.size() - 1] - 1) * (nums[nums.size() - 2] - 1);
}
int main() {
vector<int> nums = {1, 2, 3, 4};
cout << maxProduct(nums) << endl;
return 0;
}

Question 55
Problem Statement:
Find the longest common prefix string amongst an array of strings. If
there is no common prefix, return an empty string.
Input:
 An array of strings strs.
Constraints:
 1≤len(strs)≤2001 \leq \text{len(strs)} \leq 200
 0≤len(strs[i])≤2000 \leq \text{len(strs[i])} \leq 200
Output:
 Return the longest common prefix.
Sample Input
["flower","flow","flight"]
Sample Output
"fl"
Solution (C++)
#include <bits/stdc++.h>
using namespace std;
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";

string prefix = strs[0];

for (int i = 1; i < strs.size(); i++) {
while (strs[i].find(prefix) != 0) {
prefix = prefix.substr(0, prefix.length() - 1);
}
}
return prefix;
}

int main() {
vector<string> strs = {"flower", "flow", "flight"};
cout << longestCommonPrefix(strs) << endl;
return 0;
}

Question 56
Problem Statement:
Reverse a linked list.
Input:
 A singly linked list.
Constraints:
 1≤len(linked list)≤1051 \leq \text{len(linked list)} \leq 10^5
Output:
 Return the reversed linked list.
Sample Input
1 -> 2 -> 3 -> 4 -> 5
Sample Output
5 -> 4 -> 3 -> 2 -> 1
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};

ListNode* reverseList(ListNode* head) {

ListNode* prev = NULL;
ListNode* curr = head;

while (curr != NULL) {

ListNode* nextNode = curr->next;
 curr->next = prev;
prev = curr;
curr = nextNode;
}

return prev;
}

int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);

ListNode* newHead = reverseList(head);

while (newHead != NULL) {

cout << newHead->val << " ";
newHead = newHead->next;
}
cout << endl;

return 0;
}

Question 57
Problem Statement:
Find the kth largest element in an unsorted array.
Input:
 An array of integers nums and an integer k.
Constraints:
 1≤k≤len(nums)≤1041 \leq k \leq \text{len(nums)} \leq 10^4
 −104≤nums[i]≤104-10^4 \leq \text{nums[i]} \leq 10^4
Output:
 Print the kth largest element in the array.
Sample Input
[3, 2, 1, 5, 6, 4]
k=2
Sample Output
5
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int findKthLargest(vector<int>& nums, int k) {

priority_queue<int> pq;
for (int num : nums) {
 pq.push(num);
}

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

pq.pop();
}

return pq.top();
}

int main() {
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;

cout << findKthLargest(nums, k) << endl;

return 0;
}

Question 58
Problem Statement:
Given a string s and a dictionary of words wordDict, determine if the
string can be segmented into a space-separated sequence of one or
more dictionary words.
Input:
 A string s and a list wordDict of words.
Constraints:
 1≤len(s)≤10001 \leq \text{len(s)} \leq 1000
 1≤len(wordDict)≤10001 \leq \text{len(wordDict)} \leq 1000
Output:
 Return true if the string can be segmented, otherwise return
false.
Sample Input
s = "leetcode"
wordDict = ["leet", "code"]
Sample Output
true
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {

unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.length() + 1, false);
dp[0] = true;

for (int i = 1; i <= s.length(); i++) {

for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
dp[i] = true;
 break;
}
}
}

return dp[s.length()];
}

int main() {
string s = "leetcode";
vector<string> wordDict = {"leet", "code"};

cout << (wordBreak(s, wordDict) ? "true" : "false") << endl;

return 0;
}

Question 59
Problem Statement:
Given an array of integers nums, find the number of subarrays with
sum equal to k.
Input:
 An array of integers nums and an integer k.
Constraints:
 1≤len(nums)≤2×1041 \leq \text{len(nums)} \leq 2 \times 10^4
 −107≤nums[i]≤107-10^7 \leq \text{nums[i]} \leq 10^7
Output:
 Return the number of subarrays that sum to k.
Sample Input
nums = [1, 1, 1], k = 2
Sample Output
2
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int subarraySum(vector<int>& nums, int k) {

unordered_map<int, int> map;
int count = 0, sum = 0;

map[0] = 1;

for (int num : nums) {

sum += num;
if (map.find(sum - k) != map.end()) {
count += map[sum - k];
}
map[sum]++;
}
 return count;
}

int main() {
vector<int> nums = {1, 1, 1};
int k = 2;

cout << subarraySum(nums, k) << endl;

return 0;
}

Question 60
Problem Statement:
Given a list of integers nums, find the peak element. An element is a
peak if it is greater than its neighbors.
Input:
 An array of integers nums.
Constraints:
 1≤len(nums)≤10001 \leq \text{len(nums)} \leq 1000
 1≤nums[i]≤1061 \leq \text{nums[i]} \leq 10^6
Output:
 Return the index of a peak element.
Sample Input
[1, 2, 3, 1]
Sample Output
2
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int findPeakElement(vector<int>& nums) {

int left = 0, right = nums.size() - 1;

while (left < right) {

int mid = left + (right - left) / 2;

if (nums[mid] > nums[mid + 1]) {

right = mid;
} else {
left = mid + 1;
}
}

return left;
}

int main() {
vector<int> nums = {1, 2, 3, 1};
cout << findPeakElement(nums) << endl;
 return 0;
}

Question 61
Problem Statement:
Given an integer n, generate all the valid parentheses combinations.
Input:
 An integer n.
Constraints:
 1≤n≤101 \leq n \leq 10
Output:
 Return a list of all combinations of well-formed parentheses.
Sample Input
n=3
Sample Output
["((()))", "(()())", "(())()", "()(())", "()()()"]
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

void generateParenthesis(int n, int open, int close, string s,

vector<string>& result) {
if (open == n && close == n) {
result.push_back(s);
return;
 }

if (open < n) {
generateParenthesis(n, open + 1, close, s + "(", result);
}

if (close < open) {

generateParenthesis(n, open, close + 1, s + ")", result);
}
}

vector<string> generateParenthesis(int n) {
vector<string> result;
generateParenthesis(n, 0, 0, "", result);
return result;
}

int main() {
int n = 3;
vector<string> result = generateParenthesis(n);

for (string s : result) {

cout << s << " ";
}
 cout << endl;

return 0;
}

Question 62
Problem Statement:
Given a string s, determine if it is a palindrome, considering only
alphanumeric characters and ignoring cases.
Input:
 A string s.
Constraints:
 0≤len(s)≤1050 \leq \text{len(s)} \leq 10^5
Output:
 Return true if s is a palindrome, otherwise return false.
Sample Input
"A man, a plan, a canal: Panama"
Sample Output
true
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string s) {
int left = 0, right = s.length() - 1;
 while (left < right) {
if (!isalnum(s[left])) {
left++;
} else if (!isalnum(s[right])) {
right--;
} else if (tolower(s[left]) != tolower(s[right])) {
return false;
} else {
left++;
right--;
}
}

return true;
}

int main() {
string s = "A man, a plan, a canal: Panama";
cout << (isPalindrome(s) ? "true" : "false") << endl;
return 0;
}
Question 63
Problem Statement:
Given a non-empty array nums of integers, find the maximum sum of
a non-empty subarray.
Input:
 An array of integers nums.
Constraints:
 1≤len(nums)≤1051 \leq \text{len(nums)} \leq 10^5
 −104≤nums[i]≤104-10^4 \leq \text{nums[i]} \leq 10^4
Output:
 Return the maximum sum of the subarray.
Sample Input
[1, -2, 3, 4, -1, 2, 1, -5, 4]
Sample Output
8
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int>& nums) {

int maxSum = nums[0], currentSum = nums[0];

for (int i = 1; i < nums.size(); i++) {

currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
 }

return maxSum;
}

int main() {
vector<int> nums = {1, -2, 3, 4, -1, 2, 1, -5, 4};
cout << maxSubArray(nums) << endl;
return 0;
}

Question 64
Problem Statement:
Given a 2D matrix, find the sum of the elements in the submatrix
from (row1, col1) to (row2, col2), inclusive.
Input:
 A 2D matrix matrix and four integers row1, col1, row2, col2.
Constraints:
 1≤rows,cols≤1041 \leq \text{rows}, \text{cols} \leq 10^4
Output:
 Return the sum of the elements in the submatrix.
Sample Input
matrix = [
[1, 2, 3],
[4, 5, 6],
 [7, 8, 9]
]
row1 = 0, col1 = 0, row2 = 2, col2 = 2
Sample Output
45
Solution (C++)
#include <bits/stdc++.h>
using namespace std;

class NumMatrix {
public:
vector<vector<int>> prefixSum;

NumMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();
prefixSum.resize(rows + 1, vector<int>(cols + 1, 0));

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

for (int j = 1; j <= cols; j++) {
prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] +
prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
}
}
}
 int sumRegion(int row1, int col1, int row2, int col2) {
return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1]
- prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
}
};

int main() {
vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8,
9}}; NumMatrix numMatrix(matrix); cout <<
numMatrix.sumRegion(0, 0, 2, 2) << endl; // Output: 45 return 0; }

---