TCS TAG test 12.01.2026
- Posted
- 7 Feb 2026
Summary
This post details my experience with a TCS TAG test, which featured two algorithmic challenges: finding prime factors of an integer and identifying a continuous subarray for maximum profit under a cost constraint. I provided multiple approaches and C++ solutions for both problems.
How it went
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
Questions asked (2)
- 01
Prime Factors of an Integer
Data Structures & Algorithms ยท Medium
Given an integer
n, print its prime factors in ascending order.
Example:Input: 36 Output: 2 2 3 3 - 02
Maximum Profit from Continuous Subarray with Cost Constraint
Data Structures & Algorithms ยท Medium
You are given:
โข An integerWโ maximum allowed total cost
โข An arraycost[]of sizen
โข An arrayprofit[]of sizen
You must select a continuous subarray such that:sum(cost in subarray) โค W
Among all such subarrays, return the maximum total profit.
ExampleW = 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