These are the three problems we solve live in the free masterclass How to Crack TCS CodeVita Season 14. Each one teaches one of the lessons that decide CodeVita results: read the statement exactly, let the constraints choose your algorithm, and do not trust a greedy idea until you have tried to break it.
Try each problem yourself before scrolling to the solutions. Every solution below, in C++ and Python, passes the full set of hidden tests. For the contest itself, our TCS CodeVita Season 14 guide covers the dates, rules and a preparation plan.
Problem 1: Metro card recharge (easy)
Riya's metro card starts with balance B. Before each trip, if the balance is less than the fare, she recharges by exactly R rupees, again and again until the balance covers the fare. Then the fare is deducted.
Input: the first line has B, R and T (0 ≤ B ≤ 106, 1 ≤ R ≤ 104, 1 ≤ T ≤ 100000). The second line has the T fares (1 ≤ fare ≤ 10^4).
Output: two numbers: how many recharges she made, and the final balance.
Example 1
Input:
20 50 5
15 30 40 10 60
Output:
3 15
Example 2
Input:
100 10 3
20 30 40
Output:
0 10
Hint: simulate the trips in order. Before each trip, how many recharges are needed? Can you work it out with one formula instead of a loop?
Problem 2: Signal towers (medium)
A row of N radio towers stands along a highway. A tower's signal is picked up by the first tower to its right that is strictly taller. For each tower, print how many positions away that tower is, or -1 if no taller tower stands to its right.
Input: the first line has N (1 ≤ N ≤ 100000). The second line has N heights (1 ≤ height ≤ 10^9).
Output: N numbers on one line, separated by spaces.
Example 1
Input:
6
3 1 4 2 5 5
Output:
2 1 2 1 -1 -1
Example 2
Input:
4
9 7 5 3
Output:
-1 -1 -1 -1
Hint: the obvious solution checks every tower to the right of each tower. Look at the limit on N. How many steps would that take for 100,000 towers?
Problem 3: Vending machine change (medium)
A vending machine holds unlimited coins of K denominations. Find the minimum number of coins that add up to exactly A, or print -1 if it cannot be done.
Input: the first line has K and A (1 ≤ K ≤ 50, 1 ≤ A ≤ 100000). The second line has the K denominations (1 ≤ value ≤ 100000).
Output: one number.
Example 1
Input:
4 11
1 5 6 9
Output:
2
Example 2
Input:
2 7
4 6
Output:
-1
Hint: "always take the biggest coin that fits" feels right. Try it on the first example before you trust it.
How to approach any CodeVita problem
- Read the input and output format twice. Most wrong answers come from printing the wrong thing, not from the algorithm.
- Check the constraints before writing code. N up to 100,000 rules out anything that compares every pair (about 5 billion steps).
- Work the examples by hand. If you cannot get the sample output on paper, your code will not either.
- Think of the nasty cases: the smallest input, all values equal, values in decreasing order, an impossible case that needs -1.
- Use fast input and output in C++ (
ios::sync_with_stdio(false); cin.tie(nullptr);).
Solutions
1. Metro card recharge
Simulate each trip. When the balance is short, the number of recharges needed is the shortfall divided by R, rounded up. In integer maths, ceil(x / r) is (x + r - 1) / r. A loop that adds one recharge at a time also works, but the formula cannot run slowly when the fare is far above the balance.
C++
#include <iostream>
using namespace std;
int main() {
long long b, r, t;
cin >> b >> r >> t;
long long recharges = 0;
for (long long i = 0; i < t; i++) {
long long fare; cin >> fare;
if (b < fare) {
long long k = (fare - b + r - 1) / r; // ceil((fare - b) / r)
recharges += k;
b += k * r;
}
b -= fare;
}
cout << recharges << " " << b << endl;
}
Python
b, r, t = map(int, input().split())
fares = list(map(int, input().split()))
recharges = 0
for fare in fares:
if b < fare:
k = (fare - b + r - 1) // r # ceil((fare - b) / r)
recharges += k
b += k * r
b -= fare
print(recharges, b)
Time: O(T), one pass over the trips.
2. Signal towers
First idea (too slow): for each tower, scan to the right until you find a taller one.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; cin >> n;
vector<long long> h(n);
for (auto& x : h) cin >> x;
for (int i = 0; i < n; i++) {
int ans = -1;
for (int j = i + 1; j < n; j++)
if (h[j] > h[i]) { ans = j - i; break; }
cout << ans << (i + 1 < n ? ' ' : '\n');
}
}
This is correct, but when the heights are in decreasing order every scan goes to the end: about N²/2 steps. For N = 100,000 that is 5 billion comparisons. On our machine it took 1.57 seconds even in C++, already over a typical 1-second limit.
Better idea: walk left to right keeping a stack of towers that have not yet found a taller one. When a new tower arrives, it is the answer for every shorter tower on top of the stack, so pop them and record the distance. Each tower is pushed and popped at most once, so the whole thing is O(N): 0.09 seconds for the same 100,000 towers.
C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
vector<long long> h(n);
for (auto& x : h) cin >> x;
vector<int> ans(n, -1);
stack<int> st; // towers still waiting for a taller one
for (int i = 0; i < n; i++) {
while (!st.empty() && h[st.top()] < h[i]) {
ans[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? ' ' : '\n');
}
Python
n = int(input())
h = list(map(int, input().split()))
ans = [-1] * n
stack = [] # towers still waiting for a taller one
for i in range(n):
while stack and h[stack[-1]] < h[i]:
j = stack.pop()
ans[j] = i - j
stack.append(i)
print(*ans)
This "monotonic stack" pattern solves a whole family of problems: next greater element, stock spans, largest rectangle in a histogram. It is worth knowing by heart.
3. Vending machine change
The trap: greedy, always taking the largest coin that fits.
k, a = map(int, input().split())
coins = sorted(map(int, input().split()), reverse=True)
count = 0
for c in coins:
count += a // c
a %= c
print(count if a == 0 else -1)
On the first example (A = 11, coins 1, 5, 6, 9) greedy takes 9 + 1 + 1 = 3 coins, but 5 + 6 = 2 coins is better. Greedy only works for special coin systems like Indian currency; in a contest you cannot assume it.
The fix: dynamic programming. Let best[v] be the fewest coins that make exactly v. Then best[0] = 0, and for every v, best[v] = 1 + min(best[v - c]) over every coin c that fits. Fill the table from 1 up to A; if best[A] was never reached, print -1.
C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int k, a; cin >> k >> a;
vector<int> coins(k);
for (auto& c : coins) cin >> c;
const int INF = INT_MAX;
vector<int> best(a + 1, INF);
best[0] = 0;
for (int v = 1; v <= a; v++)
for (int c : coins)
if (c <= v && best[v - c] != INF)
best[v] = min(best[v], best[v - c] + 1);
cout << (best[a] == INF ? -1 : best[a]) << endl;
}
Python
k, a = map(int, input().split())
coins = list(map(int, input().split()))
INF = float("inf")
best = [0] + [INF] * a
for v in range(1, a + 1):
for c in coins:
if c <= v and best[v - c] + 1 < best[v]:
best[v] = best[v - c] + 1
print(best[a] if best[a] != INF else -1)
Time: O(A × K), at most 100,000 × 50 = 5 million steps, comfortably fast.
Keep practising
- Take the free, timed TCS CodeVita mock test: 6 problems, judged on hidden tests, like the real round.
- Want a structured six weeks of this? The TCS CodeVita Bootcamp with C++ and DSA starts on 28 October, with a quiz after every module and two mock contests reviewed in class.
GeeksArray and ConfidentHire Academy are not affiliated with TCS. TCS CodeVita is a contest run by Tata Consultancy Services.
Comments (0)
No comments yet — be the first to share your thoughts.