Problem - 01
Given an integer n, print its prime factors in ascending order.
Example:
Input: 36 Output: 2 2 3 3
✅ Approach 1 — Brute Force (Check Prime First)
🔹 Idea
• Try every number from 2 → n
• Check if it is prime
• If prime → divide repeatedly
🔹 Complexity
O(n√n) → slow for large inputs
✅ C++ Brute Force Code
#include <iostream>
using namespace std;
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0)
return false;
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
while (n % i == 0) {
cout << i << " ";
n /= i;
}
}
if (n == 1) break;
}
return 0;
}✅ Approach 2 — Optimized Trial Division (Best for TCS)
🔹 Key Insight
No need to check if i is prime.
Just try dividing from 2 → √n.
If i were composite, its smaller prime factor would already have divided n.
🔹 Complexity
O(√n) → safe for large values
✅ C++ Optimized Code (Recommended)
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
for (long long i = 2; i * i <= n; i++) {
while (n % i == 0) {
cout << i << " ";
n /= i;
}
}
if (n > 1)
cout << n;
return 0;
}✅ Extra Optimized Version (Even Faster — Skip Evens)
After removing factor 2 → check only odd numbers.
✅ C++ Faster Variant
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
// handle factor 2
while (n % 2 == 0) {
cout << 2 << " ";
n /= 2;
}
// check only odd numbers
for (long long i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
cout << i << " ";
n /= i;
}
}
if (n > 1)
cout << n;
return 0;
}✅ Edge Cases Covered
n = 1 → prints nothing n = prime → prints n n = power → prints repeated factors n = large → uses long long
Problem-02
You are given:
• An integer W → maximum allowed total cost
• An array cost[] of size n
• An array profit[] of size n
You must select a continuous subarray such that:
sum(cost in subarray) ≤ W
Among all such subarrays, return the maximum total profit.
✅ Example
W = 10 cost = [2, 3, 5, 4] profit = [6, 7, 8, 9]
Check subarrays:
[2,3,5] → cost=10 → profit=21 ✅ [3,5] → cost=8 → profit=15 [5,4] → cost=9 → profit=17
Answer = 21
✅ Key Observation
Because it must be continuous, this is NOT knapsack DP.
This is subarray with constraint → Sliding Window.
✅ Approach 1 — Brute Force
🔹 Idea
Check every possible subarray.
For each start index:
• keep adding cost & profit
• stop if cost exceeds W
• track max profit
🔹 Complexity
O(n²)
Works only for small n.
✅ C++ Brute Force Code
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> cost(n), profit(n);
for(int i = 0; i < n; i++) cin >> cost[i];
for(int i = 0; i < n; i++) cin >> profit[i];
int maxProfit = 0;
for(int i = 0; i < n; i++) {
int sumCost = 0, sumProfit = 0;
for(int j = i; j < n; j++) {
sumCost += cost[j];
sumProfit += profit[j];
if(sumCost <= W)
maxProfit = max(maxProfit, sumProfit);
else
break;
}
}
cout << maxProfit;
}✅ Approach 2 — Optimized Sliding Window (Expected in TCS)
🔹 Why Sliding Window Works
• All values are positive (cost & profit)
• Window sum increases when right expands
• If cost exceeds W → move left pointer
🔹 Steps
left = 0
for right in range(n):
add cost[right], profit[right]
while sumCost > W:
remove cost[left], profit[left]
left++
update maxProfit🔹 Complexity: O(n)
Each element enters and leaves window once.
✅ C++ Optimized Code (Recommended)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> cost(n), profit(n);
for(int i = 0; i < n; i++) cin >> cost[i];
for(int i = 0; i < n; i++) cin >> profit[i];
int left = 0;
int sumCost = 0;
int sumProfit = 0;
int maxProfit = 0;
for(int right = 0; right < n; right++) {
sumCost += cost[right];
sumProfit += profit[right];
while(sumCost > W) {
sumCost -= cost[left];
sumProfit -= profit[left];
left++;
}
maxProfit = max(maxProfit, sumProfit);
}
cout << maxProfit;
}✅ Edge Cases TCS Might Include
W smaller than all costs → answer = 0 Single element fits → choose it All costs fit → choose whole array n = 1
