TCS TAG test 12.01.2026

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 &lt;= n; i++) {
    if (isPrime(i)) {
        while (n % i == 0) {
            cout &lt;&lt; i &lt;&lt; " ";
            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 &lt;= n; i++) {
    while (n % i == 0) {
        cout &lt;&lt; i &lt;&lt; " ";
        n /= i;
    }
}

if (n &gt; 1)
    cout &lt;&lt; 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 &lt;&lt; 2 &lt;&lt; " ";
    n /= 2;
}

// check only odd numbers
for (long long i = 3; i * i &lt;= n; i += 2) {
    while (n % i == 0) {
        cout &lt;&lt; i &lt;&lt; " ";
        n /= i;
    }
}

if (n &gt; 1)
    cout &lt;&lt; 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&lt;int&gt; cost(n), profit(n);
for(int i = 0; i &lt; n; i++) cin &gt;&gt; cost[i];
for(int i = 0; i &lt; n; i++) cin &gt;&gt; profit[i];

int maxProfit = 0;

for(int i = 0; i &lt; n; i++) {
    int sumCost = 0, sumProfit = 0;

    for(int j = i; j &lt; n; j++) {
        sumCost += cost[j];
        sumProfit += profit[j];

        if(sumCost &lt;= W)
            maxProfit = max(maxProfit, sumProfit);
        else
            break;
    }
}

cout &lt;&lt; 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&lt;int&gt; cost(n), profit(n);
for(int i = 0; i &lt; n; i++) cin &gt;&gt; cost[i];
for(int i = 0; i &lt; n; i++) cin &gt;&gt; profit[i];

int left = 0;
int sumCost = 0;
int sumProfit = 0;
int maxProfit = 0;

for(int right = 0; right &lt; n; right++) {
    sumCost += cost[right];
    sumProfit += profit[right];

    while(sumCost &gt; W) {
        sumCost -= cost[left];
        sumProfit -= profit[left];
        left++;
    }

    maxProfit = max(maxProfit, sumProfit);
}

cout &lt;&lt; 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