ACTUAL 100 TCS NQT CODING QUESTIONS (Ninja, Digital Prime)

Full Exam Format | Ninja | Digital | Prime | All Levels

LEVEL GUIDE — Know Your Tier

🟢 TCS NINJA — EASY LEVEL (Q1–Q35)

❓ Problem 1 — The Salary Table Printer

🏷️ Ninja | Number Logic | Easy

Problem Statement: Mike has started a new company and wants to print a salary table for his N employees. The salary of employee number i is computed as i × base_salary. The manager wants a neat table printed from employee 1 to N showing each employee’s number and their calculated salary.

Given N employees and a base salary B, print the salary of each employee from 1 to N.

Constraints:

1 ≤ N ≤ 100
1 ≤ B ≤ 10000

Input Format:

First line  → Integer N
Second line → Integer B (base salary)

Output Format:

N lines in format: "Employee <i>: <i*B>"

Sample Input 1:

4
500

Sample Output 1:

Employee 1: 500
Employee 2: 1000
Employee 3: 1500
Employee 4: 2000

Sample Input 2:

3
1000

Sample Output 2:

Employee 1: 1000
Employee 2: 2000
Employee 3: 3000

❓ Problem 2 — The Table Arrangement (Party Seating)

🏷️ Ninja | Math | Easy

Problem Statement: Mike has arranged a small party for the inauguration of his new startup. He has invited N employees indexed 1 to N. He wants to seat everyone at tables of size K (each table holds exactly K people). All employees must sit in index order continuously — employee 1 to K at table 1, K+1 to 2K at table 2, and so on. If the last table has fewer than K people, they still sit there.

Given N employees and table size K, print the table number for each employee.

Constraints:

1 ≤ N ≤ 1000
1 ≤ K ≤ N

Input Format:

First line  → Integer N
Second line → Integer K

Output Format:

N lines in format: "Employee <i> → Table <table_number>"

Sample Input 1:

7
3

Sample Output 1:

Employee 1 → Table 1
Employee 2 → Table 1
Employee 3 → Table 1
Employee 4 → Table 2
Employee 5 → Table 2
Employee 6 → Table 2
Employee 7 → Table 3

❓ Problem 3 — The Cyclically Rotated Array (Clockwise, First Element Fixed)

🏷️ Ninja | Array | Easy ⭐ Frequently Repeated

Problem Statement: Given an array Arr[] of N integers and a positive integer K. The task is to cyclically rotate the array clockwise by K positions. Important: Keep the first element of the array unaltered — it stays at index 0. Only elements from index 1 to N-1 are rotated.

Constraints:

1 ≤ N ≤ 1000
1 ≤ K ≤ N

Input Format:

First line  → Integer N
Second line → N space-separated integers
Third line  → Integer K

Output Format:

N space-separated integers after rotation

Sample Input 1:

5
1 2 3 4 5
2

Sample Output 1:

1 4 5 2 3

Explanation: Original sub-array (index 1 to 4): 2 3 4 5 After clockwise rotation by 2: 4 5 2 3 First element stays: 1 Final: 1 4 5 2 3

❓ Problem 4 — The Mining Camp Number System

🏷️ Ninja | Number System | Easy

Problem Statement: Workers at a mining camp use octal numbers for their inventory system (base 8). A new computer system uses decimal. The camp manager must convert all old octal inventory codes to decimal for the new system.

Given an octal number (as a string), convert it to its decimal equivalent and print it.

Constraints:

Octal string length ≤ 10
String contains only digits 0-7

Input Format:

Single line → Octal number as string

Output Format:

Single integer → Decimal equivalent

Sample Input 1:

17

Sample Output 1:

15

Sample Input 2:

144

Sample Output 2:

100

Explanation: 17 (octal) = 1×8¹ + 7×8⁰ = 8 + 7 = 15 ✅

❓ Problem 5 — The Watermark Stamp Problem

🏷️ Ninja | String | Easy ⭐ Actually Repeated in TCS Tests

Problem Statement: A document printing company adds watermarks to every page. A watermark is a string W. The company receives a document string D and wants to check how many times the watermark W appears as a substring (overlapping also counts) in D.

Given strings D and W, count the total occurrences of W in D (including overlapping ones).

Constraints:

1 ≤ len(D) ≤ 10^5
1 ≤ len(W) ≤ len(D)
Both strings contain lowercase letters only

Input Format:

First line  → String D (document)
Second line → String W (watermark)

Output Format:

Single integer → Count of occurrences (including overlapping)

Sample Input 1:

aaaa
aa

Sample Output 1:

3

Sample Input 2:

abcabcabc
abc

Sample Output 2:

3

Explanation: aa appears at positions 0, 1, 2 in aaaa → 3 times (overlapping counted).

❓ Problem 6 — The Sports Score Tracker

🏷️ Ninja | Conditional Logic | Easy

Problem Statement: In a school sports competition, teams earn points based on outcomes:

• Win → +3 points
• Draw → +1 point
• Loss → 0 points

Given the results of N matches for a team (as W, D, or L), calculate their total points and determine their ranking category:

• Points ≥ 20 → "Champion"
• 10 ≤ Points < 20 → "Qualifier"
• Points < 10 → "Eliminated"

Constraints:

1 ≤ N ≤ 50
Each result is W, D, or L

Input Format:

First line  → Integer N
Second line → N space-separated characters (W/D/L)

Output Format:

First line  → "Total Points: X"
Second line → Category

Sample Input 1:

6
W W D L W W

Sample Output 1:

Total Points: 13
Qualifier

❓ Problem 7 — The Mixed Series Nth Term

🏷️ Ninja | Series | Easy ⭐ Most Repeated TCS Question

Problem Statement: During a science experiment, a researcher identified a special mixed series: 2, 1, 6, 2, 24, 6, 120, 24, 720, 120...

On closer inspection:

• Odd-positioned terms (1st, 3rd, 5th…) follow: 2!, 4!, 6!, 8!... (even factorials)
• Even-positioned terms (2nd, 4th, 6th…) follow: 1!, 2!, 3!, 4!... (sequential factorials, one behind)

Given N (1-indexed position), find the Nth term of this series.

Constraints:

1 ≤ N ≤ 20

Input Format:

Single line → Integer N

Output Format:

Single integer → Nth term

Sample Input 1:

5

Sample Output 1:

24

Sample Input 2:

3

Sample Output 2:

6

❓ Problem 8 — The Digit Reversal Banking System

🏷️ Ninja | Number | Easy

Problem Statement: A banking system generates new account numbers by reversing the digits of a customer’s national ID and then checking if the reversed number is divisible by a given K. If divisible, the account is “Approved”, otherwise “Pending”.

Given an ID number N and a divisor K, reverse N and check divisibility.

Constraints:

1 ≤ N ≤ 10^9
1 ≤ K ≤ 100

Input Format:

First line  → Integer N (national ID)
Second line → Integer K

Output Format:

First line  → Reversed number
Second line → "Approved" or "Pending"

Sample Input 1:

1234
4

Sample Output 1:

4321
Approved

Explanation: Reversed: 4321. 4321 % 4 = 1… Wait → 4320 / 4 = 1080, 4321 % 4 = 1 → Pending. (Note: exact output depends on remainder check — candidate implements logic)

❓ Problem 9 — The Temperature Converter Station

🏷️ Ninja | Math | Easy

Problem Statement: A global weather station receives temperature readings in Celsius from field sensors. The international reporting system requires temperatures in both Fahrenheit and Kelvin.

Formulas:

• Fahrenheit = (C × 9/5) + 32
• Kelvin = C + 273.15

Given T temperatures in Celsius, print each converted to both Fahrenheit and Kelvin (rounded to 2 decimal places).

Constraints:

1 ≤ T ≤ 100
-273.15 ≤ C ≤ 1000

Input Format:

First line  → Integer T
Next T lines → Temperature in Celsius (float)

Output Format:

T lines in format: "C°C = F°F = K K"

Sample Input 1:

2
0
100

Sample Output 1:

0°C = 32.00°F = 273.15 K
100°C = 212.00°F = 373.15 K

❓ Problem 10 — The Spy’s Caesar Cipher

🏷️ Ninja | String | Easy

Problem Statement: In World War II, spies encrypted messages using the Caesar Cipher — shifting every letter in the message by a fixed number K positions forward in the alphabet. Non-alphabet characters remain unchanged. The cipher is case-sensitive (lowercase stays lowercase, uppercase stays uppercase). Wrap around Z back to A.

Given a message string and shift value K, encode the message.

Constraints:

1 ≤ len(message) ≤ 10^4
0 ≤ K ≤ 25

Input Format:

First line  → String (message)
Second line → Integer K (shift)

Output Format:

Single line → Encrypted message

Sample Input 1:

Hello World
3

Sample Output 1:

Khoor Zruog

Sample Input 2:

xyz
2

Sample Output 2:

zab

❓ Problem 11 — The Product of Non-Zero Elements

🏷️ Ninja | Array | Easy

Problem Statement: A factory quality control system stores component measurements in an array. Some measurements are recorded as 0 due to sensor failures and are invalid. The quality manager wants the product of all non-zero measurements to compute a quality index.

Given an array of N integers, compute and print the product of all non-zero elements. If all are zero, print 0.

Constraints:

1 ≤ N ≤ 100
0 ≤ arr[i] ≤ 1000

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

Single integer → Product of non-zero elements

Sample Input 1:

6
4 0 3 0 2 5

Sample Output 1:

120

Sample Input 2:

3
0 0 0

Sample Output 2:

0

❓ Problem 12 — The NGO Food Distribution

🏷️ Ninja | Math/Logic | Easy

Problem Statement: An NGO distributes food packets to poor children. They have F food packets and C children. They want to distribute packets equally and know how many packets each child gets and how many are leftover (remainder). If there are more packets than children, they distribute the rest to another village.

Given F packets and C children, find packets per child and leftovers.

Constraints:

1 ≤ F ≤ 10^9
1 ≤ C ≤ 10^6

Input Format:

First line  → Integer F
Second line → Integer C

Output Format:

First line  → "Each child gets: X packets"
Second line → "Leftover packets: Y"

Sample Input 1:

23
4

Sample Output 1:

Each child gets: 5 packets
Leftover packets: 3

❓ Problem 13 — The Train Schedule Conflict

🏷️ Ninja | Logic | Easy

Problem Statement: A railway system has N trains scheduled to depart. Each train has a departure time (in 24-hour format as integer, e.g., 1430 = 2:30 PM). Two trains have a conflict if they share the same departure time from the same platform. Given departure times of N trains, find how many unique departure times exist (to identify conflict-free slots).

Constraints:

1 ≤ N ≤ 1000
0 ≤ time ≤ 2359

Input Format:

First line  → Integer N
Second line → N space-separated integers (departure times)

Output Format:

Single integer → Count of unique departure times

Sample Input 1:

6
900 1000 900 1430 1000 1200

Sample Output 1:

4

❓ Problem 14 — The Odd-Even Separator

🏷️ Ninja | Array | Easy

Problem Statement: A data analyst at a survey company received N responses (integers). She wants to separate the odd and even responses — print all even numbers first (in original order), then all odd numbers (in original order). This helps her categorize results faster.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ arr[i] ≤ 10^6

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

First line  → Even numbers space-separated
Second line → Odd numbers space-separated
(If no even/odd numbers, print "None" for that line)

Sample Input 1:

7
3 6 1 8 4 7 2

Sample Output 1:

6 8 4 2
3 1 7

❓ Problem 15 — The School Bell Pattern

🏷️ Ninja | Pattern | Easy

Problem Statement: A school bell rings in a pattern that can be represented as an inverted triangle of stars. For N rows, the first row has N stars, the second has N-1, and so on down to 1 star. The pattern is left-aligned.

Constraints:

1 ≤ N ≤ 50

Input Format:

Single line → Integer N

Output Format:

N rows of stars as described

Sample Input 1:

4

Sample Output 1:

* * * *
* * *
* *
*

❓ Problem 16 — The Maximum Repeat Character

🏷️ Ninja | String | Easy

Problem Statement: A cryptography professor analyzes letter frequency in ancient scripts to break codes. Given a string, she wants to find the character that appears the maximum number of times. If there’s a tie, return the character with the smaller ASCII value (alphabetically first).

Constraints:

1 ≤ len(S) ≤ 10^5
String contains only lowercase English letters

Input Format:

Single line → String S

Output Format:

Single character → Most frequent character

Sample Input 1:

aabbccddaaa

Sample Output 1:

a

Sample Input 2:

abcabc

Sample Output 2:

a

❓ Problem 17 — The Treasure Room Number

🏷️ Ninja | Math | Easy

Problem Statement: In an ancient palace, the treasure room number is calculated by finding the sum of all prime numbers between 1 and N (inclusive). A historian needs to compute this to decode an old map.

Given N, find the sum of all prime numbers from 1 to N.

Constraints:

1 ≤ N ≤ 10^6

Input Format:

Single line → Integer N

Output Format:

Single integer → Sum of all primes ≤ N

Sample Input 1:

10

Sample Output 1:

17

Explanation: Primes ≤ 10: 2, 3, 5, 7 → Sum = 17 ✅

❓ Problem 18 — The Assembly Line Counter

🏷️ Ninja | Array | Easy

Problem Statement: An electronics factory uses an assembly line where items are labelled with integers. The quality inspector wants to know the count of items whose value is greater than the average of all items on the line.

Given an array of N item values, count how many are strictly greater than the average.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ arr[i] ≤ 10^6

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

Single integer → Count of items greater than average

Sample Input 1:

5
10 20 30 40 50

Sample Output 1:

2

Explanation: Average = 30. Items > 30: {40, 50} → Count = 2

❓ Problem 19 — The Palindrome Number Generator

🏷️ Ninja | Number | Easy

Problem Statement: A puzzle book has a chapter on palindrome numbers. The puzzle asks: given a range [A, B], list all palindrome numbers in that range. A number is a palindrome if it reads the same forward and backward.

Constraints:

1 ≤ A ≤ B ≤ 10^6

Input Format:

First line  → Integer A
Second line → Integer B

Output Format:

All palindrome numbers between A and B, space-separated.
If none exist, print "No Palindromes"

Sample Input 1:

10
30

Sample Output 1:

11 22

Sample Input 2:

100
110

Sample Output 2:

101

❓ Problem 20 — The Hexadecimal Mine Map

🏷️ Ninja | Number System | Easy

Problem Statement: Miners at a remote location use hexadecimal (base 16) maps. The surface team sends coordinates in decimal. The miners need to convert each decimal coordinate to its hexadecimal representation (uppercase letters A-F).

Given a decimal number N, convert it to hexadecimal.

Constraints:

0 ≤ N ≤ 10^9

Input Format:

Single line → Integer N

Output Format:

Uppercase hexadecimal string

Sample Input 1:

255

Sample Output 1:

FF

Sample Input 2:

16

Sample Output 2:

10

❓ Problem 21 — The Duplicate Removal Machine

🏷️ Ninja | String/Array | Easy

Problem Statement: A data cleaning company processes input strings. Their machine removes all duplicate characters from a string while preserving the order of first occurrence. The output is a string with each character appearing only once in the order they first appeared.

Constraints:

1 ≤ len(S) ≤ 10^5
String contains lowercase letters only

Input Format:

Single line → String S

Output Format:

Single line → String after removing duplicates

Sample Input 1:

programming

Sample Output 1:

progamin

Sample Input 2:

aabbccdd

Sample Output 2:

abcd

❓ Problem 22 — The Fibonacci Check at the Border

🏷️ Ninja | Number | Easy

Problem Statement: At an international border, a security system flags a traveller if their passport number is a Fibonacci number. The border officer receives a number N and must quickly determine: is it a Fibonacci number?

A Fibonacci number belongs to the sequence 0, 1, 1, 2, 3, 5, 8, 13…

Print "Fibonacci" or "Not Fibonacci".

Constraints:

0 ≤ N ≤ 10^15

Input Format:

Single line → Integer N

Output Format:

"Fibonacci" or "Not Fibonacci"

Sample Input 1:

13

Sample Output 1:

Fibonacci

Sample Input 2:

14

Sample Output 2:

Not Fibonacci

Hint: A number N is Fibonacci if and only if one or both of (5N²+4) or (5N²-4) is a perfect square.

❓ Problem 23 — The Space Colony Habitat Zones

🏷️ Ninja | Sorting | Easy

Problem Statement: NASA is planning a space colony. They have N habitat zones, each with a capacity value. The colony planner wants to assign zones in ascending order of capacity to smaller families first. Sort the zone capacities in ascending order and print them.

Use the Selection Sort algorithm (as specified by the colony’s legacy computer system).

Constraints:

1 ≤ N ≤ 1000
1 ≤ capacity[i] ≤ 10^6

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

N space-separated integers in ascending order

Sample Input 1:

5
64 25 12 22 11

Sample Output 1:

11 12 22 25 64

❓ Problem 24 — The Hospital Emergency Ward

🏷️ Ninja | Conditional | Easy

Problem Statement: A hospital emergency ward classifies patients based on their heart rate (BPM):

• BPM < 60 → "Bradycardia" (too slow)
• 60 ≤ BPM ≤ 100 → "Normal"
• BPM > 100 → "Tachycardia" (too fast)

Additionally, if the patient is above 60 years old and their BPM is outside 60–100, mark them as "High Risk" in addition to their condition.

Given age and BPM, classify the patient.

Constraints:

1 ≤ age ≤ 120
1 ≤ BPM ≤ 300

Input Format:

First line  → Integer age
Second line → Integer BPM

Output Format:

Condition and risk level (if applicable)

Sample Input 1:

65
45

Sample Output 1:

Bradycardia
High Risk

Sample Input 2:

30
80

Sample Output 2:

Normal

❓ Problem 25 — The String Compression Challenge

🏷️ Ninja | String | Easy

Problem Statement: A communication system compresses strings by replacing consecutive repeated characters with the character followed by its count. For example, aaabbc becomes a3b2c1. If the compressed string is not shorter than the original, return the original string unchanged.

Constraints:

1 ≤ len(S) ≤ 10^5
String contains lowercase English letters

Input Format:

Single line → String S

Output Format:

Compressed string or original if compression is not beneficial

Sample Input 1:

aaabbc

Sample Output 1:

a3b2c1

Sample Input 2:

abc

Sample Output 2:

abc

Explanation: abc compressed = a1b1c1 (length 6 > 3) → return original.

❓ Problem 26 — The Robot Grid Walk

🏷️ Ninja | Simulation | Easy

Problem Statement: A robot starts at position (0, 0) on an infinite grid. It receives a sequence of commands:

• N → move 1 step North (y+1)
• S → move 1 step South (y-1)
• E → move 1 step East (x+1)
• W → move 1 step West (x-1)

After executing all commands, print the final position of the robot, and whether it has returned to origin.

Constraints:

1 ≤ len(commands) ≤ 10^5

Input Format:

Single line → Command string (e.g., NESW)

Output Format:

First line  → "Position: (x, y)"
Second line → "At Origin" or "Not At Origin"

Sample Input 1:

NESW

Sample Output 1:

Position: (0, 0)
At Origin

Sample Input 2:

NNN

Sample Output 2:

Position: (0, 3)
Not At Origin

❓ Problem 27 — The Canteen Bill Splitter

🏷️ Ninja | Math | Easy

Problem Statement: N friends go out for lunch at a canteen. The total bill is B rupees. They want to split it equally. However, the canteen uses a rule: each person pays the bill rounded up to the nearest integer (ceiling). Find the total amount collected and the extra amount collected over the original bill.

Constraints:

1 ≤ N ≤ 1000
1 ≤ B ≤ 10^6

Input Format:

First line  → Integer N (friends)
Second line → Integer B (total bill)

Output Format:

First line  → "Each pays: X"
Second line → "Total collected: Y"
Second line → "Extra: Z"

Sample Input 1:

3
100

Sample Output 1:

Each pays: 34
Total collected: 102
Extra: 2

❓ Problem 28 — The Star Diamond Pattern

🏷️ Ninja | Pattern | Easy

Problem Statement: A textile designer creates fabric patterns programmatically. She wants to print a diamond pattern made of stars for N rows (N is always odd). The top half expands from 1 to N stars, the bottom half contracts from N-2 to 1 star. Each row is center-aligned (padded with spaces).

Constraints:

1 ≤ N ≤ 19 (N is odd)

Input Format:

Single line → Odd integer N

Output Format:

Diamond pattern as described

Sample Input 1:

5

Sample Output 1:

  *
 ***
*****
 ***
  *

❓ Problem 29 — The Leap Year Festival Planner

🏷️ Ninja | Conditional Logic | Easy

Problem Statement: A cultural committee plans a special festival every leap year. They receive a list of years and must identify which ones are leap years to schedule the event.

A leap year is:

• Divisible by 4
• BUT if divisible by 100, it must ALSO be divisible by 400

Given N years, print each year and whether it is a "Leap Year" or "Not a Leap Year".

Constraints:

1 ≤ N ≤ 100
1000 ≤ year ≤ 9999

Input Format:

First line  → Integer N
Next N lines → Year values

Output Format:

N lines: "YYYY: Leap Year" or "YYYY: Not a Leap Year"

Sample Input 1:

3
2000
1900
2024

Sample Output 1:

2000: Leap Year
1900: Not a Leap Year
2024: Leap Year

❓ Problem 30 — The Number Swap Without Temp Variable

🏷️ Ninja | Math/Bit | Easy

Problem Statement: Two engineers at a hardware company argue about the most efficient way to swap values of two variables without using a temporary variable. They want a program to swap two integers A and B using either arithmetic or XOR-based swapping and print the values before and after.

Constraints:

-10^9 ≤ A, B ≤ 10^9

Input Format:

First line  → Integer A
Second line → Integer B

Output Format:

"Before: A=X B=Y"
"After: A=Y B=X"

Sample Input 1:

5
10

Sample Output 1:

Before: A=5 B=10
After: A=10 B=5

❓ Problem 31 — The Charity Odd Calculator

🏷️ Ninja | Series | Easy

Problem Statement: A charity organization donates money based on odd numbers. They donate to the Nth odd number in the sequence 1, 3, 5, 7, 9… The charity manager also wants the sum of first N odd numbers (which is always N²).

Given N, print the Nth odd number and the sum of the first N odd numbers.

Constraints:

1 ≤ N ≤ 10^6

Input Format:

Single line → Integer N

Output Format:

First line  → "Nth Odd: X"
Second line → "Sum of first N odds: Y"

Sample Input 1:

5

Sample Output 1:

Nth Odd: 9
Sum of first N odds: 25

❓ Problem 32 — The String Rotation Check

🏷️ Ninja | String | Easy

Problem Statement: Two scientists are exchanging planetary coordinates encoded as strings. They discovered that their communication system sometimes rotates the string (circular shift). Given two strings S1 and S2, determine if S2 is a rotation of S1.

A rotation of abcd can be bcda, cdab, dabc, etc.

Print "Rotation" or "Not Rotation".

Constraints:

1 ≤ len(S1), len(S2) ≤ 10^5

Input Format:

First line  → String S1
Second line → String S2

Output Format:

"Rotation" or "Not Rotation"

Sample Input 1:

abcd
cdab

Sample Output 1:

Rotation

Sample Input 2:

hello
lloeh

Sample Output 2:

Not Rotation

❓ Problem 33 — The Capital Letters Counter

🏷️ Ninja | String | Easy

Problem Statement: A proofreading software checks business letters for formatting. One rule is: capital letters should not be overused. The software counts the number of uppercase letters and if they are more than 40% of total alphabets, it prints a “Format Warning”, otherwise "Format OK".

Constraints:

1 ≤ len(S) ≤ 10^5

Input Format:

Single line → String S

Output Format:

First line  → "Uppercase: X, Total Alphabets: Y"
Second line → "Format Warning" or "Format OK"

Sample Input 1:

Hello WORLD how Are you

Sample Output 1:

Uppercase: 8, Total Alphabets: 17
Format Warning

❓ Problem 34 — The Number Classification Machine

🏷️ Ninja | Number Theory | Easy

Problem Statement: A number classification machine at a research center classifies each number it receives as one of the following:

• Positive Even → "PE"
• Positive Odd → "PO"
• Negative Even → "NE"
• Negative Odd → "NO"
• Zero → "Z"

Given T numbers, classify each one.

Constraints:

1 ≤ T ≤ 100
-10^6 ≤ num ≤ 10^6

Input Format:

First line  → Integer T
Next T lines → Each number

Output Format:

T lines → Classification code for each number

Sample Input 1:

5
4
-3
0
-8
7

Sample Output 1:

PE
NO
Z
NE
PO

❓ Problem 35 — The Area Calculator Kiosk

🏷️ Ninja | Math | Easy

Problem Statement: A construction kiosk allows workers to calculate the area of various shapes. Given a shape type and its dimensions, compute the area (round to 2 decimal places):

• circle R → Area = π × R²
• rectangle L W → Area = L × W
• triangle B H → Area = 0.5 × B × H

Use π = 3.14159265

Constraints:

Shape is one of: circle, rectangle, triangle
All dimensions are positive integers ≤ 10^4

Input Format:

First line → Shape name
Next line  → Dimensions (1 or 2 integers based on shape)

Output Format:

"Area: X.XX"

Sample Input 1:

circle
7

Sample Output 1:

Area: 153.94

Sample Input 2:

triangle
10 5

Sample Output 2:

Area: 25.00

🔵 TCS DIGITAL — MEDIUM–HARD LEVEL (Q36–Q70)

❓ Problem 36 — The Linked List Reversal Engine

🏷️ Digital | Linked List | Medium

Problem Statement: A data processing system stores a sequence of transaction amounts as a singly linked list. The system needs to reverse the order of transactions for end-of-day reconciliation. Write a program to reverse a singly linked list and print the reversed sequence.

The linked list is given as an array of N values; build the linked list internally, reverse it using pointer manipulation (not by just reversing the array), and print the result.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ val[i] ≤ 10^6

Input Format:

First line  → Integer N
Second line → N space-separated integers (linked list values head to tail)

Output Format:

N space-separated integers (reversed linked list)

Sample Input 1:

5
1 2 3 4 5

Sample Output 1:

5 4 3 2 1

Sample Input 2:

1
42

Sample Output 2:

42

❓ Problem 37 — The Balanced Bracket Security Check

🏷️ Digital | Stack | Medium ⭐ Repeatedly Asked

Problem Statement: A software security tool validates code syntax. One check is to verify that all brackets are balanced. A string with brackets (, ), {, }, [, ] is balanced if:

1. Every opening bracket has a corresponding closing bracket.
2. Brackets are closed in the correct order.
3. Empty string is considered balanced.

Given a string, determine if brackets are balanced. Print "Balanced" or "Not Balanced".

Constraints:

0 ≤ len(S) ≤ 10^5
String contains only bracket characters

Input Format:

Single line → Bracket string

Output Format:

"Balanced" or "Not Balanced"

Sample Input 1:

{[()]}

Sample Output 1:

Balanced

Sample Input 2:

{[(])}

Sample Output 2:

Not Balanced

❓ Problem 38 — The Wildcard Pattern Matcher

🏷️ Digital | String/DP | Medium ⭐ Actual TCS Repeated

Problem Statement: A text search engine allows wildcard pattern matching. The wildcard character ? matches exactly one character, and * matches any sequence of characters (including empty). Given a text string T and a pattern string P, check if P matches T completely.

Print "Match" or "No Match".

Constraints:

1 ≤ len(T) ≤ 1000
1 ≤ len(P) ≤ 1000

Input Format:

First line  → Text string T
Second line → Pattern string P

Output Format:

"Match" or "No Match"

Sample Input 1:

aab
*b

Sample Output 1:

Match

Sample Input 2:

hello
he?lo

Sample Output 2:

Match

Sample Input 3:

hello
h*rld

Sample Output 3:

No Match

❓ Problem 39 — The Inventory Merge Sort

🏷️ Digital | Sorting | Medium

Problem Statement: A large e-commerce company has two sorted inventory lists from two different warehouses, each sorted in ascending order by product ID. The central system needs to merge them into one sorted list efficiently (Merge Sort merge step — O(n+m) time) for unified inventory management.

Constraints:

1 ≤ N, M ≤ 10^5
1 ≤ product_id ≤ 10^9

Input Format:

First line  → Integer N (size of list 1)
Second line → N space-separated integers (sorted)
Third line  → Integer M (size of list 2)
Fourth line → M space-separated integers (sorted)

Output Format:

(N+M) space-separated integers in sorted ascending order

Sample Input 1:

4
1 3 5 7
4
2 4 6 8

Sample Output 1:

1 2 3 4 5 6 7 8

❓ Problem 40 — The Network Queue Simulation

🏷️ Digital | Queue/Stack | Medium

Problem Statement: A network router processes data packets using a queue (FIFO). The system receives a sequence of operations:

• ENQUEUE X → Add packet with value X to the queue
• DEQUEUE → Remove and print the front packet
• PEEK → Print the front without removing
• SIZE → Print current size of queue
• ISEMPTY → Print "Empty" or "Not Empty"

Simulate the queue operations and produce the output.

Constraints:

1 ≤ operations ≤ 10^4
1 ≤ X ≤ 10^6
No DEQUEUE/PEEK on empty queue

Input Format:

First line  → Integer Q (number of operations)
Next Q lines → Each operation

Output Format:

Output for DEQUEUE, PEEK, SIZE, ISEMPTY operations (one per line)

Sample Input 1:

6
ENQUEUE 10
ENQUEUE 20
PEEK
DEQUEUE
SIZE
ISEMPTY

Sample Output 1:

10
10
1
Not Empty

❓ Problem 41 — The Hospital Appointment BFS Scheduler

🏷️ Digital | Graph/BFS | Medium

Problem Statement: A large hospital has departments connected by corridors. Given a graph of department connections, a patient starts at department 1 and wants to visit all reachable departments using BFS (shortest hop-count order). Print the BFS traversal order starting from node 1.

Constraints:

1 ≤ N ≤ 100 (departments)
0 ≤ E ≤ N*(N-1)/2 (corridors, undirected)
Graph may not be fully connected

Input Format:

First line  → Two integers N E
Next E lines → Two integers U V (undirected edge)

Output Format:

BFS traversal order starting from node 1, space-separated

Sample Input 1:

6 5
1 2
1 3
2 4
3 5
4 6

Sample Output 1:

1 2 3 4 5 6

❓ Problem 42 — The IT Department Binary Tree Level Order

🏷️ Digital | Tree/BFS | Medium

Problem Statement: An IT department stores employee hierarchy as a binary tree, where the root is the CEO. The HR team needs a level-order traversal (BFS) of this tree to generate a company org-chart floor-by-floor.

Given a binary tree via array representation (1-indexed, left child = 2i, right child = 2i+1, -1 means null), print the level-order traversal.

Constraints:

1 ≤ N ≤ 10^3
-1 represents null node

Input Format:

First line  → Integer N (number of nodes in array)
Second line → N space-separated integers (tree array, -1 = null)

Output Format:

Level-order traversal values (skip -1 nodes), space-separated

Sample Input 1:

7
1 2 3 4 5 6 7

Sample Output 1:

1 2 3 4 5 6 7

Sample Input 2:

7
1 2 3 -1 4 5 -1

Sample Output 2:

1 2 3 4 5

❓ Problem 43 — The Coin Change Minimum

🏷️ Digital | DP | Medium

Problem Statement: A cashier at a store wants to give back change of amount A using the minimum number of coins. The store has infinite supply of coins of given denominations. If it is not possible to make exact change, print -1.

Constraints:

1 ≤ number of denominations ≤ 20
1 ≤ denomination[i] ≤ 1000
1 ≤ A ≤ 10^4

Input Format:

First line  → Integer N (number of denominations)
Second line → N space-separated coin values
Third line  → Integer A (amount)

Output Format:

Single integer → Minimum coins needed, or -1 if impossible

Sample Input 1:

3
1 5 10
27

Sample Output 1:

4

Explanation: 27 = 10 + 10 + 5 + 1 + 1 → Wait, 10+10+5+1+1=27 → 5 coins. Optimal: 10+10+5+1+1=27 → min check: 10+10+7 → 10+10+5+1+1 = 5 coins (candidates compute optimal)

❓ Problem 44 — The Drone Delivery Graph DFS

🏷️ Digital | Graph/DFS | Medium

Problem Statement: A drone delivery company maps delivery zones as a directed graph. The central hub (node 1) needs to reach all delivery zones. Using DFS, determine the order drones would explore each zone. Also check if all zones are reachable from node 1; if not, print the unreachable zones.

Constraints:

1 ≤ N ≤ 100
0 ≤ E ≤ N*(N-1)
Directed graph

Input Format:

First line  → Two integers N E
Next E lines → Two integers U V (directed edge U → V)

Output Format:

First line  → "DFS: " followed by DFS order space-separated
Second line → "Unreachable: " followed by unreachable nodes, or "All Reachable"

Sample Input 1:

5 4
1 2
1 3
2 4
3 5

Sample Output 1:

DFS: 1 2 4 3 5
All Reachable

❓ Problem 45 — The Longest Common Subsequence Archive

🏷️ Digital | DP | Medium–Hard

Problem Statement: Two historians are analyzing ancient texts. They want to find the Longest Common Subsequence (LCS) between two texts (strings) — the longest sequence of characters that appears in both strings in the same order (not necessarily contiguous).

Given two strings, print the length of their LCS.

Constraints:

1 ≤ len(S1) ≤ 1000
1 ≤ len(S2) ≤ 1000

Input Format:

First line  → String S1
Second line → String S2

Output Format:

Single integer → Length of LCS

Sample Input 1:

ABCBDAB
BDCABA

Sample Output 1:

4

Explanation: LCS is BCBA or BDAB, length = 4 ✅

❓ Problem 46 — The Matrix Diagonal Sum

🏷️ Digital | Matrix | Medium

Problem Statement: A data analyst is studying a square matrix of N×N values. She wants to find the sum of both diagonals (primary and secondary), but if N is odd, the center element should be counted only once (not twice).

Constraints:

1 ≤ N ≤ 100
1 ≤ matrix[i][j] ≤ 10^6

Input Format:

First line  → Integer N
Next N lines → N space-separated integers per row

Output Format:

Single integer → Sum of both diagonals (center counted once)

Sample Input 1:

3
1 2 3
4 5 6
7 8 9

Sample Output 1:

25

Explanation: Primary diagonal: 1+5+9=15. Secondary: 3+5+7=15. Center (5) counted twice → 15+15-5=25 ✅

❓ Problem 47 — The Jump Game Solution

🏷️ Digital | Greedy/DP | Medium

Problem Statement: A video game character is positioned at index 0 of an array. Each element represents the maximum jump length from that position. The character wants to reach the last index. Determine if it is possible to reach the last index.

Print "Can Reach" or "Cannot Reach".

Constraints:

1 ≤ N ≤ 10^4
0 ≤ arr[i] ≤ 10^4

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

"Can Reach" or "Cannot Reach"

Sample Input 1:

6
2 3 1 1 4 0

Sample Output 1:

Can Reach

Sample Input 2:

6
3 2 1 0 4 0

Sample Output 2:

Cannot Reach

❓ Problem 48 — The Student Distribution Problem (Combinatorics)

🏷️ Digital | Math/Combinatorics | Hard

Problem Statement: A teacher wants to distribute N students equally into R classrooms. The number of ways to arrange students in classrooms (where arrangement within classroom matters) is calculated using a multinomial coefficient. Compute the number of ways modulo 10^9+7.

Given R rooms and N students, find the count of arrangements where students are distributed as equally as possible (some rooms get floor(N/R) students, others get ceil(N/R)).

Constraints:

1 ≤ R ≤ N ≤ 10^6

Input Format:

First line  → Integer T (test cases)
Next T lines → Two integers R N

Output Format:

T lines → Answer for each test case modulo 10^9+7

Sample Input 1:

2
3 6
2 5

Sample Output 1:

90
20

❓ Problem 49 — The Smart City Traffic Signal

🏷️ Digital | Graph/Shortest Path | Medium–Hard

Problem Statement: A smart city has N intersections and M roads. Each road has a travel time (weight). An ambulance at intersection S needs the shortest time to reach the hospital at intersection D (Dijkstra’s Algorithm).

Constraints:

1 ≤ N ≤ 1000
1 ≤ M ≤ 10^4
1 ≤ weight ≤ 10^4
1 ≤ S, D ≤ N

Input Format:

First line  → Two integers N M
Next M lines → Three integers U V W (edge from U to V with weight W, undirected)
Last line   → Two integers S D

Output Format:

Single integer → Shortest time from S to D, or -1 if unreachable

Sample Input 1:

4 4
1 2 10
1 3 5
3 2 3
2 4 1
1 4

Sample Output 1:

9

Explanation: Path 1→3→2→4: 5+3+1 = 9 (shorter than 1→2→4: 10+1=11) ✅

❓ Problem 50 — The Anagram Grouper

🏷️ Digital | String/HashMap | Medium

Problem Statement: A linguistics researcher has a list of N words. She wants to group all anagrams together and print each group on a separate line (words within a group separated by spaces, groups in order of first occurrence).

Constraints:

1 ≤ N ≤ 10^4
1 ≤ len(word) ≤ 100
Words are lowercase

Input Format:

First line  → Integer N
Second line → N space-separated words

Output Format:

Each group of anagrams on a separate line

Sample Input 1:

6
eat tea tan ate nat bat

Sample Output 1:

eat tea ate
tan nat
bat

❓ Problem 51 — The Rectangle Overlap Detector

🏷️ Digital | Geometry | Medium

Problem Statement: A GIS software system detects if two land plots (rectangles) overlap. Each rectangle is defined by its bottom-left (x1, y1) and top-right (x2, y2) coordinates. Two rectangles overlap if their intersection has positive area (touching at boundary only is NOT overlap).

Print "Overlap" or "No Overlap".

Constraints:

-10^4 ≤ coordinates ≤ 10^4

Input Format:

First line  → x1 y1 x2 y2 (Rectangle 1)
Second line → x3 y3 x4 y4 (Rectangle 2)

Output Format:

"Overlap" or "No Overlap"

Sample Input 1:

0 0 4 4
2 2 6 6

Sample Output 1:

Overlap

Sample Input 2:

0 0 2 2
3 3 5 5

Sample Output 2:

No Overlap

❓ Problem 52 — The Word Ladder Distance

🏷️ Digital | BFS/Graph | Hard

Problem Statement: In a word transformation game, a player must transform word BEGIN to word TARGET by changing exactly one letter at a time, where each intermediate word must exist in a given dictionary. Find the minimum number of steps (transformations) needed. If impossible, print 0.

Constraints:

2 ≤ word length ≤ 5 (all words same length)
1 ≤ dictionary size ≤ 500

Input Format:

First line  → String BEGIN
Second line → String TARGET
Third line  → Integer N (dictionary size)
Next N lines → Dictionary words (one per line)

Output Format:

Single integer → Minimum transformations (or 0 if impossible)

Sample Input 1:

hit
cog
6
hot
dot
dog
lot
log
cog

Sample Output 1:

5

Explanation: hit → hot → dot → dog → cog (5 steps) ✅

❓ Problem 53 — The Largest Rectangle in Histogram

🏷️ Digital | Stack | Hard

Problem Statement: An architect is analyzing a city skyline represented as a histogram (bar chart) where each bar has width 1 and a given height. She wants to find the area of the largest rectangle that can be formed within the histogram bars.

Constraints:

1 ≤ N ≤ 10^5
0 ≤ height[i] ≤ 10^4

Input Format:

First line  → Integer N
Second line → N space-separated integers (bar heights)

Output Format:

Single integer → Maximum rectangle area

Sample Input 1:

6
2 1 5 6 2 3

Sample Output 1:

10

Explanation: Bars of height 5 and 6 form a rectangle of area 10 ✅

❓ Problem 54 — The Network Infection Spread (BFS Levels)

🏷️ Digital | BFS/Graph | Medium

Problem Statement: A cybersecurity analyst is simulating a virus spread through N computers (nodes 1 to N) connected by a network graph. The virus starts at node 1 at time 0. Every second, it infects all directly connected uninfected computers simultaneously. Find the time taken to infect all computers, and if any computer is unreachable, print its list.

Constraints:

1 ≤ N ≤ 1000
Undirected graph

Input Format:

First line  → Two integers N E
Next E lines → Two integers U V (undirected edge)

Output Format:

First line  → "Infection Time: T seconds"
Second line → "Unreachable: X Y Z" or "All Infected"

Sample Input 1:

5 4
1 2
1 3
2 4
3 5

Sample Output 1:

Infection Time: 2 seconds
All Infected

❓ Problem 55 — The Maximum Path Sum in Binary Tree

🏷️ Digital | Tree/DFS | Hard

Problem Statement: A financial planning company represents investment plans as a binary tree where each node holds a profit/loss value (can be negative). An analyst wants to find the maximum path sum — the maximum sum achievable along any path from any node to any node (path must go through connected nodes, can start/end anywhere).

Constraints:

1 ≤ N ≤ 10^4
-10^4 ≤ node_val ≤ 10^4

Input Format:

First line  → Integer N
Second line → N space-separated integers (tree in level-order, -1 = null)

Output Format:

Single integer → Maximum path sum

Sample Input 1:

5
-10 9 20 -1 -1 15 7

Sample Output 1:

42

Explanation: Path: 15 → 20 → 7 = 42 ✅

❓ Problem 56 — The Minimum Spanning Tree Cost

🏷️ Digital | Graph/MST | Hard

Problem Statement: A telecom company wants to lay fibre cables connecting N cities with minimum total cable length. Given the cost of laying cable between each pair of cities, find the Minimum Spanning Tree cost using Kruskal’s or Prim’s algorithm.

Constraints:

2 ≤ N ≤ 500
Weighted undirected connected graph

Input Format:

First line  → Two integers N E
Next E lines → Three integers U V W (edge with weight)

Output Format:

Single integer → Total MST cost

Sample Input 1:

4 5
1 2 10
1 3 6
1 4 5
2 4 15
3 4 4

Sample Output 1:

19

Explanation: MST edges: 3-4(4) + 1-4(5) + 1-2(10) = 19 ✅

❓ Problem 57 — The Palindrome Partitioning Count

🏷️ Digital | DP | Hard

Problem Statement: A data encoding system partitions a string into substrings where every substring is a palindrome. The system wants to know the minimum number of cuts needed to partition a given string S such that every resulting substring is a palindrome.

Constraints:

1 ≤ len(S) ≤ 1000
String contains lowercase letters

Input Format:

Single line → String S

Output Format:

Single integer → Minimum number of cuts

Sample Input 1:

aab

Sample Output 1:

1

Explanation: aab → aa | b (1 cut) ✅

❓ Problem 58 — The Topological Sort Curriculum

🏷️ Digital | Graph/DAG | Medium–Hard

Problem Statement: A university curriculum has N courses. Some courses have prerequisites. Given a list of prerequisite pairs (A, B meaning A must be taken before B), produce a valid course order using Topological Sort. If there’s a cycle (impossible to complete all courses), print "Impossible".

Constraints:

1 ≤ N ≤ 100
Directed acyclic graph (or cyclic — candidate must detect)

Input Format:

First line  → Two integers N E
Next E lines → Two integers A B (A is prerequisite of B)

Output Format:

Space-separated topological order, or "Impossible"

Sample Input 1:

4 3
1 2
1 3
3 4

Sample Output 1:

1 3 4 2

(Any valid topological order is accepted)

❓ Problem 59 — The Flood Fill Algorithm

🏷️ Digital | Graph/DFS | Medium

Problem Statement: A paint application has a canvas represented as an N×M grid of integers (colors). A user clicks on cell (SR, SC) and selects a new color NC. The flood fill operation changes the color of the clicked cell and all adjacent (4-directional) cells with the same original color to the new color — recursively.

Print the grid after flood fill.

Constraints:

1 ≤ N, M ≤ 50
0 ≤ color ≤ 100

Input Format:

First line  → Two integers N M
Next N lines → M space-separated integers (grid)
Next line   → Three integers SR SC NC

Output Format:

N lines of M space-separated integers (modified grid)

Sample Input 1:

3 3
1 1 1
1 1 0
1 0 0
1 1 2

Sample Output 1:

2 2 2
2 2 0
2 0 0

❓ Problem 60 — The Sliding Window Maximum

🏷️ Digital | Deque | Hard

Problem Statement: A financial analyst tracks stock prices over N days. She uses a sliding window of size K to find the maximum price in each window as it moves from left to right across the data. Efficient O(n) solution is expected (use deque).

Constraints:

1 ≤ K ≤ N ≤ 10^5
1 ≤ price[i] ≤ 10^6

Input Format:

First line  → Two integers N K
Second line → N space-separated integers (prices)

Output Format:

(N-K+1) space-separated integers → Max of each window

Sample Input 1:

8 3
1 3 -1 -3 5 3 6 7

Sample Output 1:

3 3 5 5 6 7

❓ Problem 61 — The Matrix Chain Multiplication Order

🏷️ Digital | DP | Hard

Problem Statement: A computer graphics system needs to multiply a chain of N matrices. The order of multiplication affects the total number of scalar multiplications needed. Given the dimensions of N matrices (as an array where matrix i has dimensions arr[i-1] × arr[i]), find the minimum number of scalar multiplications needed.

Constraints:

2 ≤ N ≤ 100
1 ≤ arr[i] ≤ 100

Input Format:

First line  → Integer N (number of matrices)
Second line → (N+1) space-separated integers (dimension array)

Output Format:

Single integer → Minimum scalar multiplications

Sample Input 1:

3
40 20 30 10

Sample Output 1:

26000

❓ Problem 62 — The Rat in a Maze Pathfinder

🏷️ Digital | Backtracking | Medium–Hard

Problem Statement: A lab rat starts at the top-left corner of an N×N maze (cell 0,0) and needs to reach the bottom-right corner (N-1, N-1). The maze is represented as a 2D grid where 1 = open path and 0 = wall. The rat can move Down (D) or Right (R) only. Print all valid paths in lexicographic order. If no path exists, print "No Path".

Constraints:

2 ≤ N ≤ 10
maze[i][j] ∈ {0, 1}

Input Format:

First line  → Integer N
Next N lines → N space-separated integers (maze row)

Output Format:

All valid paths as strings of D/R characters, one per line

Sample Input 1:

4
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1

Sample Output 1:

DDRDRR
DDRRD

(exact output depends on direction rules — candidates compute)

❓ Problem 63 — The N-Queen Placement

🏷️ Digital | Backtracking | Hard

Problem Statement: The classic N-Queens problem: Place N queens on an N×N chessboard such that no two queens attack each other (no two in same row, column, or diagonal). Print the total number of distinct solutions.

Constraints:

1 ≤ N ≤ 12

Input Format:

Single line → Integer N

Output Format:

Single integer → Number of distinct solutions

Sample Input 1:

4

Sample Output 1:

2

Sample Input 2:

8

Sample Output 2:

92

❓ Problem 64 — The Trie-Based Autocomplete

🏷️ Digital | Trie | Hard

Problem Statement: A search engine builds an autocomplete system using a Trie data structure. Given a dictionary of N words, and Q prefix queries, for each query print all words in the dictionary that start with that prefix. If no words match, print "No Suggestions". Words should be printed in lexicographic order.

Constraints:

1 ≤ N ≤ 1000
1 ≤ Q ≤ 100
All strings contain lowercase letters

Input Format:

First line  → Integer N
Next N lines → Dictionary words
Next line   → Integer Q
Next Q lines → Prefix queries

Output Format:

For each query: matching words comma-separated, or "No Suggestions"

Sample Input 1:

5
apple
app
application
apt
bat
2
app
ba

Sample Output 1:

app,apple,application
bat

❓ Problem 65 — The Subarray Product Less Than K

🏷️ Digital | Sliding Window | Medium

Problem Statement: A factory’s production line records daily output. A quality supervisor wants to know how many contiguous subarrays have a product strictly less than K. Each element is a positive integer.

Constraints:

1 ≤ N ≤ 3 × 10^4
1 ≤ arr[i] ≤ 1000
0 < K ≤ 10^6

Input Format:

First line  → Two integers N K
Second line → N space-separated positive integers

Output Format:

Single integer → Count of subarrays with product < K

Sample Input 1:

4 100
10 5 2 6

Sample Output 1:

8

❓ Problem 66 — The Serialize and Deserialize Binary Tree

🏷️ Digital | Tree | Hard

Problem Statement: A cloud backup system serializes binary trees to strings for storage and deserializes them back. Serialize a binary tree to a comma-separated string (use "null" for missing nodes, level-order). Then deserialize back and print in-order traversal to verify correctness.

Constraints:

0 ≤ N ≤ 100 nodes
-1000 ≤ node_val ≤ 1000

Input Format:

First line  → Comma-separated serialized tree (level-order, "null" for empty)

Output Format:

First line  → Serialized string (as-is)
Second line → In-order traversal of deserialized tree

Sample Input 1:

1,2,3,null,null,4,5

Sample Output 1:

1,2,3,null,null,4,5
2 1 4 3 5

❓ Problem 67 — The Prison Break Grid

🏷️ Digital | BFS/Grid | Medium

Problem Statement: A prisoner is trapped in an N×M grid cell (SR, SC) and needs to reach the exit at (ER, EC). The grid has walls (#) and open cells (.). The prisoner can move in 4 directions (Up, Down, Left, Right). Find the minimum steps to escape, or print -1 if impossible.

Constraints:

1 ≤ N, M ≤ 200

Input Format:

First line  → Two integers N M
Next N lines → Grid rows (each character is . or #)
Next line   → SR SC ER EC (start and end positions, 0-indexed)

Output Format:

Single integer → Minimum steps, or -1

Sample Input 1:

5 5
. . . . .
. # # # .
. . . # .
# # . # .
. . . . .
0 0 4 4

Sample Output 1:

8

❓ Problem 68 — The Alien Dictionary Order

🏷️ Digital | Topological Sort | Hard

Problem Statement: Scientists discover an alien civilization’s dictionary. The dictionary is sorted in the alien language’s own alphabetical order. Given a sorted list of alien words, deduce the order of letters in the alien alphabet (topological sort on characters). If the order is ambiguous, output any valid order. If it is impossible (cycle), print "Invalid Dictionary".

Constraints:

2 ≤ N ≤ 100 words
All characters are lowercase English letters

Input Format:

First line  → Integer N
Next N lines → Alien words in sorted order

Output Format:

String → Deduced letter ordering, or "Invalid Dictionary"

Sample Input 1:

4
baa
abcd
abca
cab

Sample Output 1:

bdac

(Any valid topological order)

❓ Problem 69 — The Sudoku Validator

🏷️ Digital | Matrix/Logic | Medium

Problem Statement: A puzzle verification system checks submitted 9×9 Sudoku boards. A filled Sudoku board is valid if:

1. Each row contains digits 1–9 with no repetition
2. Each column contains digits 1–9 with no repetition
3. Each of the 9 3×3 sub-boxes contains digits 1–9 with no repetition

Print "Valid Sudoku" or "Invalid Sudoku".

Constraints:

Exactly 9 rows and 9 columns
All values are integers 1–9

Input Format:

9 lines → 9 space-separated integers per line

Output Format:

"Valid Sudoku" or "Invalid Sudoku"

Sample Input 1:

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

Sample Output 1:

Valid Sudoku

❓ Problem 70 — The Knapsack Decision

🏷️ Digital | DP/Greedy | Medium–Hard

Problem Statement: A thief is robbing a jewellery shop and can carry a bag of maximum weight capacity W. There are N items, each with a weight and a value. The thief wants to maximize the total value without exceeding W. Items cannot be split (0/1 Knapsack).

Constraints:

1 ≤ N ≤ 100
1 ≤ W ≤ 1000
1 ≤ weight[i] ≤ W
1 ≤ value[i] ≤ 10^4

Input Format:

First line  → Two integers N W
Next N lines → Two integers weight value

Output Format:

Single integer → Maximum value achievable

Sample Input 1:

4 7
1 1
3 4
4 5
5 7

Sample Output 1:

9

🔴 TCS PRIME — EXPERT LEVEL (Q71–Q100)

❓ Problem 71 — The Alien Invasion Segment Tree

🏷️ Prime | Segment Tree | Very Hard

Problem Statement: An alien tracking system monitors N radar readings. It supports two operations repeatedly in real-time:

1. UPDATE i x → Update the reading at position i to x
2. QUERY l r → Find the maximum reading in range [l, r]

Use a Segment Tree to handle both operations in O(log n).

Constraints:

1 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ i, l, r ≤ N
1 ≤ x ≤ 10^9

Input Format:

First line  → Two integers N Q
Second line → N space-separated integers (initial readings)
Next Q lines → "UPDATE i x" or "QUERY l r"

Output Format:

For each QUERY, print the maximum value on a new line

Sample Input 1:

5 4
1 3 5 7 9
QUERY 1 3
UPDATE 2 10
QUERY 1 3
QUERY 3 5

Sample Output 1:

5
10
9

❓ Problem 72 — The Magical Fenwick Tree Range Sum

🏷️ Prime | BIT/Fenwick Tree | Very Hard

Problem Statement: A financial system tracks N accounts with initial balances. It processes:

1. ADD i x → Add x to account i
2. SUM l r → Print total balance from account l to r

Use a Binary Indexed Tree (Fenwick Tree) for O(log n) per operation.

Constraints:

1 ≤ N ≤ 10^6
1 ≤ Q ≤ 10^6

Input Format:

First line  → Two integers N Q
Second line → N initial balances
Next Q lines → "ADD i x" or "SUM l r"

Output Format:

Answer for each SUM query on a new line

Sample Input 1:

5 3
1 2 3 4 5
SUM 1 3
ADD 2 5
SUM 1 3

Sample Output 1:

6
11

❓ Problem 73 — The Interstellar LRU Cache

🏷️ Prime | HashMap + Doubly Linked List | Very Hard

Problem Statement: A space station computer uses an LRU (Least Recently Used) cache of capacity C. It processes GET and PUT operations:

• GET key → Return value if exists, else return -1. Mark as recently used.
• PUT key value → Insert or update. If capacity exceeded, evict least recently used.

Implement the LRU cache and simulate all operations.

Constraints:

1 ≤ C ≤ 3000
1 ≤ operations ≤ 2 × 10^4

Input Format:

First line  → Two integers C Q
Next Q lines → "GET key" or "PUT key value"

Output Format:

For each GET, print the value or -1

Sample Input 1:

2 7
PUT 1 1
PUT 2 2
GET 1
PUT 3 3
GET 2
PUT 4 4
GET 1

Sample Output 1:

1
-1
1

❓ Problem 74 — The Maximum Flow Water Distribution

🏷️ Prime | Graph/Max Flow | Very Hard

Problem Statement: A city engineer is designing a water distribution network modelled as a directed graph with N nodes. Each edge has a maximum flow capacity. Find the maximum water flow from source (node 1) to sink (node N) using the Ford-Fulkerson algorithm.

Constraints:

2 ≤ N ≤ 50
Directed graph with capacities

Input Format:

First line  → Two integers N E
Next E lines → Three integers U V C (directed edge from U to V with capacity C)

Output Format:

Single integer → Maximum flow from 1 to N

Sample Input 1:

6 9
1 2 16
1 3 13
2 3 10
2 4 12
3 2 4
3 5 14
4 3 9
4 6 20
5 6 4

Sample Output 1:

23

❓ Problem 75 — The String Hashing Anti-Plagiarism

🏷️ Prime | Hashing/Rolling Hash | Hard

Problem Statement: A university anti-plagiarism system detects if any substring of document A of length L exactly matches any substring of document B of length L. Use Rabin-Karp rolling hash for efficiency. Print the starting indices (0-based) in both documents where the first match is found, or "No Match".

Constraints:

1 ≤ len(A), len(B) ≤ 10^5
1 ≤ L ≤ min(len(A), len(B))

Input Format:

First line  → String A
Second line → String B
Third line  → Integer L

Output Format:

"Match at A[i] and B[j]" or "No Match"

Sample Input 1:

abcxyz
xyzabc
3

Sample Output 1:

Match at A[0] and B[3]

❓ Problem 76 — The Minimum Cost to Hire Workers

🏷️ Prime | Greedy/Heap | Hard

Problem Statement: A company wants to hire exactly K workers from a pool of N workers. Each worker has a quality and a wage expectation. The company must pay each worker at least their expected wage AND proportional to quality (all workers in the group are paid at the same wage-to-quality ratio). Find the minimum cost to hire exactly K workers (output as a float rounded to 5 decimal places).

Constraints:

1 ≤ K ≤ N ≤ 10^4
1 ≤ quality[i] ≤ 10^4
1 ≤ wage[i] ≤ 10^4

Input Format:

First line  → Two integers N K
Next N lines → Two integers quality wage

Output Format:

Minimum cost rounded to 5 decimal places

Sample Input 1:

3 2
10 70
20 50
5 30

Sample Output 1:

105.00000

❓ Problem 77 — The Burrows-Wheeler String Transform

🏷️ Prime | String/Cyclic Rotation | Very Hard

Problem Statement: The Burrows-Wheeler Transform (BWT) is used in data compression. Given a string S, generate all rotations, sort them lexicographically, and output the last column of the sorted rotation matrix. Also output the row index where the original string appears in the sorted order (0-indexed).

Constraints:

1 ≤ len(S) ≤ 1000
String contains lowercase letters only

Input Format:

Single line → String S

Output Format:

First line  → BWT string (last column)
Second line → Index of original string

Sample Input 1:

banana

Sample Output 1:

annb$aa

(Standard BWT appends $ to mark end — candidates follow convention)

❓ Problem 78 — The Minimum Edit Distance Engine

🏷️ Prime | DP | Hard

Problem Statement: A spell-checker computes how many minimum operations (insert, delete, or replace one character) are needed to transform word A into word B. This is the Edit Distance (Levenshtein Distance). Given two words, compute it.

Constraints:

0 ≤ len(A), len(B) ≤ 1000

Input Format:

First line  → String A
Second line → String B

Output Format:

Single integer → Minimum edit distance

Sample Input 1:

horse
ros

Sample Output 1:

3

Sample Input 2:

intention
execution

Sample Output 2:

5

❓ Problem 79 — The Tarjan’s SCC Finder

🏷️ Prime | Graph/DFS/SCC | Very Hard

Problem Statement: A telecommunications company has N servers connected by directed links. They want to identify Strongly Connected Components (SCCs) — groups of servers where every server can reach every other server in the group. Use Tarjan’s Algorithm and print each SCC.

Constraints:

1 ≤ N ≤ 1000
Directed graph

Input Format:

First line  → Two integers N E
Next E lines → Two integers U V (directed edge)

Output Format:

Print each SCC on a separate line (nodes space-separated, in any order)

Sample Input 1:

5 5
1 2
2 3
3 1
3 4
4 5

Sample Output 1:

1 2 3
4
5

❓ Problem 80 — The Convex Hull Security Perimeter

🏷️ Prime | Geometry/Convex Hull | Very Hard

Problem Statement: A military base needs to erect a fence around all its watchtowers. Given N watchtower coordinates, find the minimum perimeter fence that encloses all towers — i.e., the Convex Hull of the points. Use Graham Scan or Jarvis March. Print the vertices of the convex hull in counter-clockwise order starting from the bottom-most point, and the perimeter length rounded to 2 decimal places.

Constraints:

3 ≤ N ≤ 10^4
0 ≤ x, y ≤ 10^4

Input Format:

First line  → Integer N
Next N lines → Two integers x y (coordinates)

Output Format:

First line  → Convex hull vertices (x,y pairs) in CCW order
Second line → "Perimeter: X.XX"

Sample Input 1:

5
0 0
1 1
2 2
0 2
2 0

Sample Output 1:

(0,0) (2,0) (2,2) (0,2)
Perimeter: 8.00

❓ Problem 81 — The Alien Number Theory (Big Modular Exponentiation)

🏷️ Prime | Math/Number Theory | Hard

Problem Statement: A cryptography algorithm requires computing (A^B) mod M where A and B can be extremely large. Brute force is too slow — use fast modular exponentiation (binary exponentiation) to compute it efficiently in O(log B) time.

Constraints:

1 ≤ A ≤ 10^18
1 ≤ B ≤ 10^18
1 ≤ M ≤ 10^9

Input Format:

Three integers on separate lines: A, B, M

Output Format:

Single integer → (A^B) mod M

Sample Input 1:

2
10
1000

Sample Output 1:

24

Sample Input 2:

3
200
1000000007

Sample Output 2:

884337246

❓ Problem 82 — The Longest Increasing Subsequence with Count

🏷️ Prime | DP | Hard

Problem Statement: A stock analyst is analyzing stock prices over N days. She wants to find both the length of the Longest Increasing Subsequence (LIS) and the number of such subsequences of that length. Print both values. Count modulo 10^9+7.

Constraints:

1 ≤ N ≤ 2000
1 ≤ price[i] ≤ 10^9

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

First line  → "LIS Length: X"
Second line → "Count: Y"

Sample Input 1:

6
1 3 5 4 7 8

Sample Output 1:

LIS Length: 5
Count: 2

❓ Problem 83 — The Painter’s Partition Problem

🏷️ Prime | Binary Search + Greedy | Hard

Problem Statement: N boards need to be painted. There are K painters. Each painter can paint contiguous boards only. The time taken to paint a board = board length. All painters work simultaneously. Minimize the time taken by the slowest painter (i.e., minimize the maximum sum of any contiguous partition of N boards into K groups).

Constraints:

1 ≤ K ≤ N ≤ 10^4
1 ≤ board[i] ≤ 10^6

Input Format:

First line  → Two integers N K
Second line → N space-separated integers (board lengths)

Output Format:

Single integer → Minimum time (maximum partition sum minimized)

Sample Input 1:

4 2
10 20 30 40

Sample Output 1:

60

Explanation: Optimal partition: [10,20,30] and [40] → max(60,40) = 60 ✅

❓ Problem 84 — The Interval Scheduling Meeting Rooms

🏷️ Prime | Greedy/Sorting | Hard

Problem Statement: A conference centre manager receives N meeting requests. Each meeting has a start and end time. She wants to find the minimum number of meeting rooms required to accommodate all meetings (no two meetings in the same room can overlap).

Constraints:

1 ≤ N ≤ 10^5
0 ≤ start[i] < end[i] ≤ 10^9

Input Format:

First line  → Integer N
Next N lines → Two integers start end

Output Format:

Single integer → Minimum rooms required

Sample Input 1:

4
0 30
5 10
15 20
5 25

Sample Output 1:

3

❓ Problem 85 — The Regular Expression Matcher

🏷️ Prime | DP/String | Very Hard

Problem Statement: Implement a regular expression matcher supporting:

• . → Matches any single character
• * → Matches zero or more of the preceding element

The match must cover the entire input string (not partial). Print "Match" or "No Match".

Constraints:

0 ≤ len(s), len(p) ≤ 1000
s contains lowercase letters
p contains lowercase letters, '.', '*'

Input Format:

First line  → String s (text)
Second line → String p (pattern)

Output Format:

"Match" or "No Match"

Sample Input 1:

aa
a*

Sample Output 1:

Match

Sample Input 2:

ab
.*

Sample Output 2:

Match

Sample Input 3:

aab
c*a*b

Sample Output 3:

Match

❓ Problem 86 — The Minimum Window Substring

🏷️ Prime | Sliding Window | Hard

Problem Statement: A search engine’s highlight feature needs to find the minimum window substring of string S that contains all characters of string T (including duplicates). If no valid window exists, print "".

Constraints:

1 ≤ len(S) ≤ 10^5
1 ≤ len(T) ≤ 10^4

Input Format:

First line  → String S
Second line → String T

Output Format:

Minimum window substring, or "" if not possible

Sample Input 1:

ADOBECODEBANC
ABC

Sample Output 1:

BANC

Sample Input 2:

a
aa

Sample Output 2:

❓ Problem 87 — The Number of Islands (Union-Find)

🏷️ Prime | Union-Find/DFS | Hard

Problem Statement: A geographer is analysing satellite images. A 2D grid contains 1 (land) and 0 (water). An island is a group of 1s connected horizontally or vertically. Count the total number of distinct islands. Use Union-Find (Disjoint Set Union) for maximum efficiency.

Constraints:

1 ≤ N, M ≤ 300
grid[i][j] ∈ {0, 1}

Input Format:

First line  → Two integers N M
Next N lines → M space-separated integers (0 or 1)

Output Format:

Single integer → Number of islands

Sample Input 1:

4 5
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

Sample Output 1:

1

Sample Input 2:

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Sample Output 2:

3

❓ Problem 88 — The Traveling Salesman Problem (Small N)

🏷️ Prime | DP/Bitmask | Very Hard

Problem Statement: A delivery agent starts from city 0 and must visit all N cities exactly once, then return to city 0. Given the distance matrix, find the minimum total travel distance (TSP using Bitmask DP for N ≤ 20).

Constraints:

2 ≤ N ≤ 15
0 ≤ distance[i][j] ≤ 10^4
distance[i][i] = 0

Input Format:

First line  → Integer N
Next N lines → N space-separated integers (distance matrix row i)

Output Format:

Single integer → Minimum tour distance

Sample Input 1:

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Sample Output 1:

80

❓ Problem 89 — The Suffix Array Construction

🏷️ Prime | String/Suffix Array | Very Hard

Problem Statement: A bioinformatics tool indexes DNA sequences using a Suffix Array — an array of the starting indices of all suffixes of a string, sorted in lexicographic order. Given a DNA string S, construct and output its suffix array.

Constraints:

1 ≤ len(S) ≤ 10^5
String contains only A, C, G, T

Input Format:

Single line → DNA string S

Output Format:

Space-separated integers → Suffix array (starting indices 0-indexed)

Sample Input 1:

ACGT

Sample Output 1:

0 1 2 3

Sample Input 2:

banana

Sample Output 2:

5 3 1 0 4 2

❓ Problem 90 — The Count of Inversions (Merge Sort)

🏷️ Prime | Divide & Conquer | Hard

Problem Statement: A stock market analyst counts inversions in a price array — a pair (i, j) where i < j but arr[i] > arr[j] represents a bad trend. Count the total number of inversions using modified Merge Sort in O(n log n).

Constraints:

1 ≤ N ≤ 10^5
1 ≤ arr[i] ≤ 10^9

Input Format:

First line  → Integer N
Second line → N space-separated integers

Output Format:

Single integer → Number of inversions

Sample Input 1:

5
2 4 1 3 5

Sample Output 1:

3

Explanation: Inversions: (2,1), (4,1), (4,3) → 3 ✅

❓ Problem 91 — The Skip List Implementation

🏷️ Prime | Advanced Data Structure | Very Hard

Problem Statement: A database system uses a Skip List for fast search, insert, and delete. Implement a Skip List and simulate Q operations:

• INSERT x → Insert value x
• DELETE x → Delete value x (if exists)
• SEARCH x → Print "Found" or "Not Found"
• PRINT → Print all elements in sorted order

Constraints:

1 ≤ Q ≤ 10^4
1 ≤ x ≤ 10^6

Input Format:

First line  → Integer Q
Next Q lines → Operation and value

Output Format:

Output for SEARCH and PRINT operations

Sample Input 1:

6
INSERT 5
INSERT 3
INSERT 7
SEARCH 3
DELETE 3
PRINT

Sample Output 1:

Found
5 7

❓ Problem 92 — The Game Theory Nim Problem

🏷️ Prime | Game Theory | Hard

Problem Statement: Two players play Nim: there are N piles of stones. Players take turns. On each turn a player removes any positive number of stones from exactly one pile. The player who takes the last stone wins. Both players play optimally.

Given the pile sizes, determine who wins: “First Player Wins” or “Second Player Wins”.

The optimal strategy uses XOR: if XOR of all pile sizes ≠ 0, first player wins.

Constraints:

1 ≤ N ≤ 100
0 ≤ pile[i] ≤ 10^9

Input Format:

First line  → Integer N
Second line → N space-separated pile sizes

Output Format:

"First Player Wins" or "Second Player Wins"

Sample Input 1:

3
3 4 5

Sample Output 1:

First Player Wins

Sample Input 2:

3
1 2 3

Sample Output 2:

Second Player Wins

Explanation: XOR(3,4,5) = 2 ≠ 0 → First wins. XOR(1,2,3) = 0 → Second wins.

❓ Problem 93 — The Shortest Superstring

🏷️ Prime | DP/Greedy | Very Hard

Problem Statement: A DNA sequencing lab receives N DNA fragments. They want to reconstruct the shortest possible DNA strand that contains all fragments as substrings. This is the Shortest Superstring Problem. For small N (≤ 12), use Bitmask DP. Return the minimum length of such a superstring.

Constraints:

1 ≤ N ≤ 12
1 ≤ len(each fragment) ≤ 50

Input Format:

First line  → Integer N
Next N lines → DNA fragments

Output Format:

Single integer → Minimum superstring length

Sample Input 1:

3
abcd
cdef
efgh

Sample Output 1:

8

Explanation: Superstring: abcdefgh length 8 (cd overlaps, ef overlaps) ✅

❓ Problem 94 — The Segment Overlap Merge

🏷️ Prime | Sorting/Intervals | Hard

Problem Statement: A video editing software has N timeline clips, each represented as an interval [start, end]. The software needs to merge all overlapping clips into the minimum number of non-overlapping intervals. Two intervals overlap if one starts before the other ends (or they touch at a boundary).

Constraints:

1 ≤ N ≤ 10^4
0 ≤ start ≤ end ≤ 10^4

Input Format:

First line  → Integer N
Next N lines → Two integers start end

Output Format:

Merged intervals, one per line: "start end"

Sample Input 1:

5
1 3
2 6
8 10
15 18
9 12

Sample Output 1:

1 6
8 12
15 18

❓ Problem 95 — The K-th Smallest in Matrix

🏷️ Prime | Binary Search/Heap | Hard

Problem Statement: A satellite imaging system stores data in an N×N matrix where each row and column is sorted in ascending order. Given K, find the K-th smallest element in the matrix.

Constraints:

1 ≤ N ≤ 300
1 ≤ K ≤ N²
-10^9 ≤ matrix[i][j] ≤ 10^9

Input Format:

First line  → Two integers N K
Next N lines → N space-separated integers per row

Output Format:

Single integer → K-th smallest element

Sample Input 1:

3 8
1 5 9
10 11 13
12 13 15

Sample Output 1:

13

❓ Problem 96 — The 2-SAT Boolean Satisfiability

🏷️ Prime | Graph/SCC | Very Hard

Problem Statement: A circuit designer has N boolean variables and M clauses, each of the form (xi OR xj) or (xi OR ¬xj) or (¬xi OR ¬xj). This is the 2-SAT Problem. Determine if there exists a valid assignment of True/False to all variables that satisfies all clauses. If yes, print "Satisfiable" and a valid assignment; else "Unsatisfiable". Solve using SCC + Topological Sort.

Constraints:

1 ≤ N ≤ 10^4
1 ≤ M ≤ 10^5

Input Format:

First line  → Two integers N M
Next M lines → Two integers i j
(positive = xi, negative = ¬xi)

Output Format:

"Satisfiable" + assignment on next line, or "Unsatisfiable"

Sample Input 1:

2 3
1 2
-1 2
1 -2

Sample Output 1:

Satisfiable
x1=True x2=True

❓ Problem 97 — The Heavy-Light Decomposition

🏷️ Prime | Tree/HLD | Very Hard

Problem Statement: A power grid is modelled as a tree of N nodes (power stations). Maintenance engineers make two types of queries repeatedly:

1. UPDATE u v x → Add x to all nodes on the path from u to v
2. QUERY u v → Find the maximum node value on the path from u to v

Use Heavy-Light Decomposition + Segment Tree for O(log² n) per query.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ initial_value ≤ 10^6

Input Format:

First line  → Two integers N Q
Second line → N initial node values
Next (N-1) lines → Edges of the tree
Next Q lines → "UPDATE u v x" or "QUERY u v"

Output Format:

Answer for each QUERY on a new line

Sample Input 1:

5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
QUERY 4 5
UPDATE 1 3 10
QUERY 1 3

Sample Output 1:

5
13

❓ Problem 98 — The Persistent Segment Tree

🏷️ Prime | Persistent DS | Very Hard

Problem Statement: A version-controlled database needs to answer historical range minimum queries. The database has N initial values and supports:

• UPDATE v i x → Create version v from version (v-1) by updating index i to x
• QUERY v l r → In version v, find the minimum value in range [l, r]

Use a Persistent Segment Tree to store all versions efficiently.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^4

Input Format:

First line  → Two integers N Q
Second line → N initial values (version 0)
Next Q lines → "UPDATE i x" or "QUERY v l r"

Output Format:

Answer for each QUERY on a new line

Sample Input 1:

4 4
1 3 5 7
QUERY 0 1 4
UPDATE 2 10
QUERY 0 1 4
QUERY 1 1 4

Sample Output 1:

1
1
3

❓ Problem 99 — The Polynomial Multiplication via FFT

🏷️ Prime | FFT/Math | Very Hard

Problem Statement: A signal processing system needs to multiply two large polynomials. Given polynomial A of degree N and polynomial B of degree M (both given as coefficient arrays), compute A × B using the Fast Fourier Transform (FFT) in O((N+M) log(N+M)). Print the coefficients of the resulting polynomial from degree 0 to degree N+M.

Constraints:

1 ≤ N, M ≤ 10^5
0 ≤ coefficient ≤ 100

Input Format:

First line  → Integer N (degree of A)
Second line → (N+1) space-separated integers (coefficients of A, from degree 0)
Third line  → Integer M (degree of B)
Fourth line → (M+1) space-separated integers (coefficients of B)

Output Format:

(N+M+1) space-separated integers → Coefficients of A×B

Sample Input 1:

2
1 2 1
2
1 1 1

Sample Output 1:

1 3 4 3 1

Explanation: (1 + 2x + x²)(1 + x + x²) = 1 + 3x + 4x² + 3x³ + x⁴ ✅

❓ Problem 100 — The Final Boss: Offline LCA + Difference Array on Tree

🏷️ Prime | Tree/LCA/Euler Tour | Very Hard

Problem Statement: A research institute models dependency relationships as a rooted tree (root = node 1) with N nodes. A professor issues Q queries, each of the form (u, v, x): add x to every node on the path from u to v. After all updates, print the final value of each node.

Use:

• Binary Lifting for O(log n) LCA
• Euler Tour + Difference Array on Tree for path updates in O(N + Q log N)

Constraints:

1 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ x ≤ 10^4

Input Format:

First line  → Two integers N Q
Next (N-1) lines → Edges of the tree (undirected)
Next Q lines → Three integers u v x

Output Format:

N space-separated integers → Final value of each node (1 to N)

Sample Input 1:

5 2
1 2
1 3
2 4
2 5
1 4 5
3 5 3

Sample Output 1:

8 8 3 5 8

Explanation: Path 1→4: nodes {1,2,4} += 5. Path 3→5: nodes {3,1,2,5} += 3. Final: node1=8, node2=8, node3=3, node4=5, node5=8 ✅

COMPLETE 100-QUESTION MASTER TABLE