Problem Statement

You are given distance (in kilometers) and time (in minutes). Convert time into hours and calculate the speed in km/h.

Speed = Distance / Time (in hours)

Constraints

• Time must be in the range 1 to 60 minutes (inclusive).
• If time is outside this range, print "Error".
• Output speed should be an integer (floor value).

Example

Input:
Distance = 30
Time = 30

Output:
60

Explanation:
Time in hours = 30 / 60 = 0.5
Speed = 30 / 0.5 = 60

Test Cases

Problem Statement

Given an integer array (can contain both positive and negative numbers), find the maximum subarray sum and the subarray itself. Use Kadane's algorithm.

Output Format

Maximum Subarray: <sum>, Subarray: [elements]

Example

Input:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output:
Maximum Subarray: 6, Subarray: [4, -1, 2, 1]

Test Cases

Problem Statement

You are given a 2D matrix representing marks of students. Each row represents a student, and each column represents marks in exams.

• Column 0 - Internal exam marks
• Column 1 - External exam marks

You are also given an index (i, j). Calculate the total marks (internal + external) of the student at row i.

Input Explanation

• Two integers R and C representing number of rows and columns.
• A 2D matrix of size R x C containing marks.
• Two integers i and j representing the index of the student.

Note: The student is identified by row i. The marks are taken from column 0 and column 1.

Output Explanation

• Print the sum of internal and external marks of the selected student.
• If the index is invalid (out of bounds), print "Invalid Input".

Example

Input:
2 2
40 50
30 60
1 1

Output:
90

Explanation:
Student at index (1,1) -> row = 1
Internal = 30, External = 60
Total = 90

Problem Statement

You are given efficiencies of n people. You need to form groups of size t. If some people are left (n is not divisible by t), those extra people are removed.

For each group, find the difference between the highest and lowest efficiency. Return the maximum difference among all groups.

Input Explanation

• Integer n - number of people
• Array of n integers - efficiencies
• Integer t - size of each group

Output Explanation

• Form groups of size t after sorting the array.
• For each group, compute difference = max element - min element.
• Print the maximum difference among all groups.
• If input is invalid, print "Invalid Input".

Example

Input:
6
1 3 4 9 10 12
2

Output:
5

Explanation:
Sorted array: [1, 3, 4, 9, 10, 12]
Groups: (1,3) -> 2, (4,9) -> 5, (10,12) -> 2
Maximum difference = 5

Problem Statement

Given an array of elements, remove all duplicate elements while preserving the order of their first occurrence. After removing duplicates, print the resulting array in reverse order.

Input Format

• First line contains an integer n (size of the array).
• Second line contains n space-separated integers.

Output Format

• Print the array after removing duplicates and reversing it.

Example

Input:
 7
 1 2 3 2 4 1 5

Output:
 5 4 3 2 1

Explanation:
Original array: 1 2 3 2 4 1 5
After removing duplicates: 1 2 3 4 5
Reverse the array: 5 4 3 2 1

Problem Statement

A sorted array is rotated k times in a clockwise direction. Given this rotated array of size N and a target element K:

• Find the number of rotations performed on the original sorted array.
• Find the index of element K in the original (sorted) array.

If the element is not present, return -1.

Input Format

• First line contains an integer N (size of array).
• Second line contains N space-separated integers (rotated sorted array).
• Third line contains an integer K (target element).

Output Format

• First output: Number of rotations.
• Second output: Index of K in the original sorted array.

Example

Input:
 7
 4 5 6 7 1 2 3
 2

Output:
 4
 1

Explanation:
Original sorted array: 1 2 3 4 5 6 7
Rotated array: 4 5 6 7 1 2 3
Number of rotations = index of minimum element = 4
Element 2 is at index 1 in original sorted array

Approach

• The number of rotations = index of the minimum element.
• To find index in original array, sort the array or map rotated index using the rotation count.

Problem Statement

Given an array of integers, count the frequency of each element and return the element that has the highest frequency. If multiple elements have the same highest frequency, return the smallest element among them.

Input Format

• First line: Integer n (size of array).
• Second line: n space-separated integers.

Output Format

• Single integer: element with highest frequency (smallest if tie).

Example

Input:
 6
 1 3 2 3 4 1

Output:
 1

Explanation:
Frequency: 1 -> 2, 3 -> 2, 2 -> 1, 4 -> 1
Both 1 and 3 have same frequency (2), smallest is 1.

Problem Statement

You are given an integer n, an array cost[] of size n, and an n x n symmetric matrix where diagonal elements are 0. For each row, replace the diagonal element (0) with cost[i] and compute the sum of that row. Return the minimum row sum among all rows.

Input Format

• First line: Integer n.
• Second line: n space-separated integers (cost array).
• Next n lines: n integers each (matrix).

Output Format

• Single integer: minimum row sum.

Example

Input:
 3
 5 6 7
 0 1 3
 1 0 2
 3 2 0

Output:
 9

Explanation:
Row 0 -> replace 0 with 5 -> [5,1,3] -> sum = 9
Row 1 -> replace 0 with 6 -> [1,6,2] -> sum = 9
Row 2 -> replace 0 with 7 -> [3,2,7] -> sum = 12
Minimum = 9

Problem Statement

You are given an array of integers. Implement a modified Quick Sort partition step to determine the pivot index after placing the pivot element in its correct sorted position. The pivot is chosen as the last element of the array.

• All elements smaller than the pivot are on the left.
• All elements greater than or equal to the pivot are on the right.

Return the final index of the pivot.

Input Format

n
a1 a2 a3 ... an

• n -> size of array
• ai -> elements of array

Output Format

pivot_index

Example

Input:
5
4 2 7 1 3

Process:
Pivot = 3
After partition -> [2, 1, 3, 4, 7]

Output:
2

Approach

• Choose last element as pivot.
• Maintain index i for smaller elements.
• Traverse array: if element < pivot, swap and increment i.
• Place pivot at correct position (i + 1).
• Return pivot index.

Problem Statement

You are given a graph with n nodes and m edges. Each edge has a weight. Find the minimum cost to connect all nodes using Kruskal's algorithm. If it is not possible to connect all nodes, return -1.

Input Format

n m
u1 v1 w1
u2 v2 w2
...
um vm wm

• n -> number of nodes
• m -> number of edges
• ui, vi -> nodes connected
• wi -> weight of edge

Output Format

minimum_cost

Example

Input:
4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Output:
19

Explanation:
Edges chosen:
(2,3) -> 4
(0,3) -> 5
(0,1) -> 10
Total = 19

Approach

• Sort edges by weight.
• Use Disjoint Set (Union-Find) to avoid cycles.
• Pick smallest edges until n - 1 edges selected.
• If less than n - 1 edges, return -1.

Problem Statement

You are given a purchase amount. Based on the amount, a discount is applied as follows:

• If amount < 1000 -> 5% discount
• If amount >= 1000 and < 5000 -> 10% discount
• If amount >= 5000 -> 15% discount

Calculate the final payable amount after applying the discount.

Input Format

• A single integer amount representing the total purchase value.

Output Format

• Print the final amount after discount, rounded to 2 decimal places.

Sample Test Cases

Test Case 1:
Input:
800
Output:
760.00

Test Case 2:
Input:
2000
Output:
1800.00

Test Case 3:
Input:
6000
Output:
5100.00

Problem Statement

A king wants to arrange his army in a line following strict rules. You are given:

• N -> total number of soldiers in the arrangement
• R -> soldiers are numbered from 1 to R
• end -> the last soldier in the arrangement must be this number

Rules:

• The arrangement must start with soldier 1.
• The arrangement must end with soldier end.
• No two adjacent soldiers can have the same number.
• You can use any soldier number from 1 to R multiple times.

Find the total number of valid arrangements of length N.

Input Format

• Three integers: N R end

Output Format

• A single integer: number of valid arrangements

Sample Test Cases

Test Case 1:
Input:
4 4 3
Output:
7

Test Case 2:
Input:
3 3 2
Output:
2

Approach (Dynamic Programming)

• dp[i][j] = number of ways to form a sequence of length i ending with soldier j.
• Transition: dp[i][j] += dp[i-1][k] where k != j.
• Initialization: dp[1][1] = 1 (must start with 1).
• Answer: dp[N][end].

Brute Force Idea

• Generate all sequences of length N using numbers from 1 to R.
• Check: first element is 1, last element is end, and no adjacent duplicates.
• Complexity: Time O(R^N), Space O(N).

Problem Statement

A parking system calculates fines based on the number of hours a vehicle is parked. Given an integer hours representing parking duration, calculate the fine:

• If parking time <= 2 hours, fine = 100
• If parking time > 2 and <= 5 hours, fine = 50
• If parking time > 5 hours, fine = 20

Input

• An integer hours

Output

• An integer representing the fine

Test Cases

Input: 2
Output: 100

Input: 4
Output: 50

Input: 6
Output: 20

Problem Statement

You are given an array of integers of size n and an integer maxSum. Find the maximum possible sum of elements from the array such that the sum is less than or equal to maxSum. You can choose any subset of elements.

Input

• Integer n (size of array)
• Array arr[n]
• Integer maxSum

Output

• Maximum possible sum <= maxSum

Test Cases

Test Case 1
Input:
n = 4
arr = [2, 3, 5, 7]
maxSum = 10
Output:
10
Explanation: subset {3, 7} gives sum 10.

Test Case 2
Input:
n = 3
arr = [4, 8, 6]
maxSum = 9
Output:
8
Explanation: best subset is {8}.

Approach (Brute Force)

• Generate all subsets.
• Compute sum for each subset.
• Track maximum sum <= maxSum.

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) that has the largest product, and return that product.

Test Cases

Input: [2, 3, -2, 4]
Output: 6

Input: [-2, 0, -1]
Output: 0

Input: [-2, -3, -4]
Output: 12

Problem Statement

Given two arrays s and x of size n containing the same elements (possibly in different order), you can perform adjacent swaps on array s. Find the minimum number of adjacent swaps required to transform s into x. If it is not possible, return -1.

Test Cases

Input:
n = 5
s = [20, 40, 29, 10, 98]
x = [10, 98, 40, 20, 29]

Output:
7

Problem Statement

A movie theatre has ticket prices stored in an array of size N. Find all odd ticket prices and compute the sum, count, and average of odd prices.

Input Format

• First line: Integer N (number of ticket prices)
• Second line: N space-separated integers (ticket prices)

Output Format

• Print 3 values: sum count average
• Average should be printed with 2 decimal places

Example

Input:
4
20 25 30 35

Output:
60 2 30.00

Problem Statement

You are given BreadCost[] and FillingCost[] arrays and an integer Target. You need to make a sandwich such that total cost is closest to Target.

• You must choose exactly one bread.
• You can choose 0, 1, or more fillings.
• Each filling can be used at most 2 times.
• If two costs are equally close, return the smaller one.

Input Format

• First line: BreadCost array
• Second line: FillingCost array
• Third line: Target

Output Format

• Print a single integer representing the closest cost

Example

Input:
BreadCost = [5, 7]
FillingCost = [2, 3]
Target = 10

Output:
10

Approach Explanation

• Try each bread as a starting cost.
• For each filling, choose 0, 1, or 2 times (DFS recursion).
• Track the closest cost to target, preferring smaller if tied.
• Time complexity: O(B * 3^F).

Problem Statement

You are given 10 predefined ranks in ascending order: 1 2 3 4 5 6 7 8 9 10. Take an integer N as input.

• If N is not in the range 1 to 10, print "Invalid Input".
• Otherwise, print the Nth smallest rank and the Nth largest rank on the same line separated by a space.

Input Format

• A single integer N.

Output Format

• Print "Invalid Input" if N is not between 1 and 10.
• Otherwise print: NthSmallest NthLargest

Constraints

• 1 <= N <= 10

Example 1

Input:
3

Output:
3 8

Example 2

Input:
11

Output:
Invalid Input

Problem Statement

You are given N (number of boxes), W (maximum total weight allowed in one group), and N integers representing weights of boxes. Boxes must be taken in order.

Rules:

• Add boxes one by one into the current group.
• Total weight of a group cannot exceed W.
• If adding the next box exceeds W, stop immediately.
• You cannot skip any box.
• Count number of complete groups formed and number of boxes used until stopping point.

Print both values.

Input Format

N W
W1 W2 W3 ... WN

Output Format

number_of_groups boxes_used

Example 1

Input:
6 10
2 3 4 5 1 2

Output:
2 6

Example 2

Input:
5 7
2 3 5 4 2

Output:
2 3

Problem Statement

You are given N pairs of integers (a, b). Sort the pairs using Selection Sort based on these rules:

• Sort in ascending order of the first element.
• If first elements are equal, sort by the second element in ascending order.

Input Format

• First line contains an integer N (number of pairs).
• Next N lines each contain two integers a and b.

Output Format

• Print the sorted pairs, one per line.

Example

Input:
5
10 4
3 2
5 2
3 1
10 5

Output:
3 1
3 2
5 2
10 4
10 5

Approach (Selection Sort)

• Iterate through array.
• Select minimum element based on the conditions.
• Swap with current index.

Problem Statement

You are given an undirected weighted graph. Find the Minimum Spanning Tree (MST) and the Second Minimum Spanning Tree. The second MST must be strictly greater than the MST and minimum among all such spanning trees.

Input Format

• First line: N M (number of cities, number of connections).
• Next M lines: u v w (edge between u and v with weight w).

Output Format

• Print two integers: MST weight and Second MST weight.

Constraints

• 1 <= N <= 100
• 1 <= M <= 1000
• Graph is connected

Example

Input:
4 5
1 2 1
1 3 2
2 3 1
2 4 3
3 4 4

Output:
5 6

Approach

• Find MST using Kruskal's Algorithm (sort edges, Union-Find).
• For each edge in MST, remove it and recompute MST.
• Track minimum valid result greater than MST.

Problem Statement

You are given a 3 x 3 matrix. Determine whether the matrix forms a trapezoid pattern.

• The top row has more non-zero elements than the bottom row.
• Elements decrease as we move downward.

If the matrix is a trapezoid, print the sum of the first row elements. Otherwise, print the product of the first row elements.

Input

3 x 3 matrix elements

Output

Sum or Product of first row

Example 1

Input:
1 2 3
4 5 0
6 0 0

Output:
6

Example 2

Input:
1 2 3
4 5 6
7 8 9

Output:
6

Problem Statement

A medical store maintains a digital database of medicines with unique ID and stock level.

• 2 -> Full stock
• 1 -> Half stock
• 0 -> Out of stock

Count medicines by stock level and print whether reorder is required.

Input

• n (number of medicines)
• Next n lines: id stock_level

Output

• Full stock count
• Half stock count
• Out of stock count
• Status message

Example

Input:
5
101 2
102 1
103 0
104 2
105 1

Output:
Full: 2
Half: 2
Out: 1
Reorder Required

Problem Statement

A gym offers membership plans based on months:

• months <= 0 -> Invalid Input
• 1 -> 2000
• 2 to 3 -> 5000
• 4 to 6 -> 9000
• more than 6 -> 15000

Print "Invalid Input" or "Cost: <amount>".

Input Format

• A single integer months

Sample Test Cases

Input:
1
Output:
Cost: 2000

Input:
3
Output:
Cost: 5000

Input:
5
Output:
Cost: 9000

Input:
7
Output:
Cost: 15000

Input:
0
Output:
Invalid Input

Problem Statement

The system processes N transactions. Each transaction has sender, receiver, timestamp, and amount.

Rules:

• If any transaction has the same sender and receiver as a previous transaction, print "Error: Duplicate Transaction" and terminate.
• If the difference between timestamps of any two consecutive transactions is greater than 60 seconds, print "Fraud Detected" and terminate.
• If all transactions are valid, print "All Transactions Valid".

Input Format

• First line: Integer N
• Next N lines: sender receiver timestamp amount

Output Format

• "Error: Duplicate Transaction"
• "Fraud Detected"
• "All Transactions Valid"

Sample Test Cases

Test Case 1
Input:
3
A B 10 100
C D 50 200
E F 100 300
Output:
All Transactions Valid

Test Case 2
Input:
3
A B 10 100
C D 50 200
A B 70 300
Output:
Error: Duplicate Transaction

Test Case 3
Input:
3
A B 10 100
C D 50 200
E F 200 300
Output:
Fraud Detected

Problem Statement

You are given an integer N (minimum charge required) and an array of integers representing the charge in each laptop. Count how many laptops have charge >= N.

Input Format

N
A1 A2 A3 A4 ... An

• N -> minimum required charge
• Ai -> charge of each laptop

Output Format

Single integer -> number of laptops that can work

Example

Input:
5
2 3 6 7 1

Output:
2

Problem Statement

You are given an integer N, representing the number of people initially in the Happy state. At each iteration:

• From Happy: 70% become Sad, 30% remain Happy.
• From Sad: 50% remain Sad, 50% become Happy.

Simulate this process for 4 iterations and print final Happy and Sad counts.

Input Format

A single integer N

Output Format

Final_Happy Final_Sad

Constraints

• 1 <= N <= 10^7