TCS Code Vita 8 Questions

1. Exchange Digits

Problem Description

Compute nearest larger number by interchanging digits updated.

Given 2 numbers a and b find the smallest number greater than b by interchanging the digits of a and if not possible print -1.

Constraints

1 <= a,b <= 10000000

Input Format

2 numbers, a and b, separated by space.

Output

A single number, greater than than b.

If not possible, print -1.

Test Case Explanation

Example 1

Input 
459 500

Output

549

Example 2

Input

645757 457765

Output

465577

Example 3

Input

5964 9984

Output

-1

2.Min Combinations

Problem Description

Alexander The great, while roaming the stretch of Turkey, came across a wise man.

He asked the wise man, "Who is the greatest conqueror of all?". The wise man replied, "A person with great strength and intelligence. Whosoever can solve my puzzle will go on to become the greatest!". The puzzle is as follows; Given two integers 'n1' and 'n2', select two integers 'a' and 'b', such as to solve the equation (n1 * a + n2 * b = x). But there is a catch, 'x' is the smallest positive integer which satisfies the equation. Can you help Alexander become the greatest?

Constraints

1 <= T <= 1000

-10^7 <= a, b <= 10^7

0 <= n1, n2 <= 10^7

Input Format

The first line contains the number of Test cases T.

Next T lines contains two space-separated integers, n1 and n2.

Output

Print the value of x.

Test Case Explanation

Example 1

Input

1

34818 45632

Output

2

Explanation

Given n1 = 34818 and n2 = 45632, if we choose a = 3553 and b = -2711, we get

=> n1 * a + n2 * b = x

=> 34818 * 3553 + 45632 * (-2711)

=> 2

Note: No other value of a and b, within the range, will give smaller value than 2.

3.Television Sets

Problem Description

Dr. Vishnu is opening a new world class hospital in a small town designed to be the first preference of the patients in the city. Hospital has N rooms of two types - with TV and without TV, with daily rates of R1 and R2 respectively.

However, from his experience Dr. Vishnu knows that the number of patients is not constant throughout the year, instead it follows a pattern. The number of patients on any given day of the year is given by the following formula –

(6-M)^2 + |D-15| where

M is the number of month (1 for jan, 2 for feb ...12 for dec) and

D is the date (1,2...31).

All patients prefer without TV rooms as they are cheaper, but will opt for with TV rooms only if without TV rooms are not available. Hospital has a revenue target for the first year of operation. Given this target and the values of N, R1 and R2 you need to identify the number of TVs the hospital should buy so that it meets the revenue target. Assume the Hospital opens on 1st Jan and year is a non-leap year.

Constraints

Hospital opens on 1st Jan in an ordinary year

5 <= Number of rooms <= 100

500 <= Room Rates <= 5000

0 <= Target revenue < 90000000

Input Format

First line provides an integer N that denotes the number of rooms in the hospital

Second line provides two space-delimited integers that denote the rates of rooms with TV (R1) and without TV (R2) respectively

Third line provides the revenue target

Output

Minimum number of TVs the hospital needs to buy to meet its revenue target. If it cannot achieve its target, print the total number of rooms in the hospital.

Test Case

Explanation

Example 1

Input

20

1500 1000

7000000

Output

14

Explanation

Using the formula, number of patients on 1st Jan will be 39, on 2nd Jan will be 38 and so on. Considering there are only twenty rooms and rates of both type of rooms are 1500 and 1000 respectively, we will need 14 TV sets to get revenue of 7119500. With 13 TV sets Total revenue will be less than 7000000

Example 2

Input

10

1000 1500

10000000

Output

10

Explanation

In the above example, the target will not be achieved, even by equipping all the rooms with TV. Hence, the answer is 10 i.e. total number of rooms in the hospital.

4.Petrol Pump

Problem Description

A big group of students, starting a long journey on different set of vehicles need to fill petrol in their vehicles.

As group leader you are required to minimize the time they spend at the petrol pump to start the journey at the earliest. You will be given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the petrol pump. You need to arrange the vehicles in such a way that they take shortest possible time to fill all the vehicles and provide the time taken in seconds as output. Machine vends petrol @ 1litre/second.

Assume that there is no time lost between switching vehicles to start filling petrol.

Constraints

1<= Number of vehicles < 50.

0 <= Quantity of petrol required in any vehicle <= 200

Input Format

First line will provide the quantity of petrol (separated by space) that can be filled in each vehicle.

Output

Shortest possible time to fill petrol in all the vehicles.

Test Case Explanation

Example 1

Input

1 2 3 4 5 10 11 3 6 16

Output

31

Explanation

First Petrol vending machine will cater to vehicles taking - 16, 6, 4, 3, 2 litres of petrol (Total 31 sec)

Second machine will cater to vehicles taking - 11, 10, 5, 3, 1 litres of petrol (Total 30 sec)

Example 2

Input

25 30 35 20 90 110 45 70 80 12 30 35 85

Output

335

Explanation

First Petrol vending machine will cater to vehicles taking - 80, 45, 35, 30, 25, 12, 85, 20 litres of petrol.

Second machine will cater to vehicles taking - 90, 70, 35, 30, 110 litres of petrol. Since second machine will take more time, total time to fill petrol in all vehicles will be 335 seconds.

5.War Companion

Problem Description

Infinity War is Over. Thanos has successfully collected all the Infinity Stones and wiped out half the population of the universe. Now the world depends on the remaining Avengers to bring back their loved ones.

To get a last chance of defeating Thanos, the Avengers has put together a team of its best warriors to try to steal the Infinity Gauntlet and restore order to the universe. The warriors must be put in pairs into its warships and sent out. Obviously, the team size is even.

Each warrior in the warship needs to work well with his partner in the warship, and chemistry between them is important. Hence the Supreme Commander has requested all the warriors to give a list of the remaining warriors in the team in the order of their preferring to work with them.

Using these lists the Supreme Commander needs to create a set of suitable pairs of warriors, with each warrior getting a partner. A set of pairings of warriors is not suitable if two warriors exist who both prefer each other more than their existing partner. The Supreme Commander recognizes that there can be more than one set of suitable pairs of warriors. He ranks the warriors in descending order of competence, so that the most competent are at the top. He has directed you, his chief analyst, to create a suitable set of pairings that lets the most competent warrior to partner someone as high in list of preferences as possible, and then the next most competent warrior to work with as high a person on his list as possible, and so on.

Please write a program to create a suitable set of pairings that meets the Supreme Commander’s directions. If no such pairing exits, indicate that.

Constraints

N <= 10

Input Format

First line contains the number of warriors (N).

Next N lines contain the preference list of N warriors, where the first word in the line is the warrior and the next (N-1) words are the warriors in the preference order.

The N lines give the warriors in order of decreasing competence

Output

A set of suitable pairs as directed by the Supreme Commander. If no suitable sets exist, output “No Suitable Pairs.”.

Test Case Explanation

Example 1

Input

6

Ironman Thor Blackwidow Hawkeye Hulk Captainamerica

Thor BlackwidowCaptainamerica Hawkeye Ironman Hulk

Hulk BlackwidowCaptainamerica Hawkeye Ironman Thor

Blackwidow Hawkeye Hulk Ironman Captainamerica Thor

Captainamerica Hawkeye Hulk Blackwidow Thor Ironman

Hawkeye Ironman Thor Blackwidow Hulk Captainamerica

Output

Ironman,Hawkeye

Thor,Captainamerica

Hulk,Blackwidow

Explanation

This is a suitable set of pairs. If we take a pair of warriors, say Thor and Blackwidow,though Thor prefers Blackwidow to his current partner (Captainamerica), Blackwidow prefers the current partner(Hulk) to Thor. Similarly all other pairs of warriors can be checked to see that this is a suitable set of pairings.

Example 2

Input

4

Charles Wolverine Jean Deadpool

Wolverine Jean Charles Deadpool

Jean Charles Wolverine Deadpool

Deadpool Charles Wolverine Jean

Output

No Suitable Pairs.

Explanation

It can be seen that there is no suitable set of pairings. If Deadpool is paired with say Charles, and the other two paired with each other, consider the warriors Charles and Jean. Charles prefers Jean to his current partner, Deadpool, and Jean prefers Charles to the current partner, Wolverine. Hence this is not a suitable pairing. Similarly, Deadpool cannot be paired with anyone else to form a suitable set. Thus the output is “No Suitable Pairs”

6.Hermoine Number

Problem Description

Voldemort is finally dead. Hermoine is bored and has now developed some interest in mathematics, so she keeps challenging her friends. Harry is now one of the victims to those hard problems and needs your help to solve this puzzle.

She calls the result to be Hermoine Number H.

Since H can be large, you need to print the result modulo MOD = 1000000007

Constraints

N <= 10^5

A[i] <= 10^5

Input Format

First line provides an integer N denoting number of elements in Array A

Second line provides N space separated values for the array A,

Third Line provides an integer denoting Query (q) corresponding the problem statement

Next q lines contain two numbers l, r denoting the values mentioned above in the statement

Output

q lines containing the value of H mod 1000000007

Test Case Explanation

Example 1

Input

5

1 2 3 4 5

2

2 2

2 4

Output

1

82944

Example 2

Input

10

77883 48760 68269 31574 57351 20528 45398 54148 37399 31382

10

5 9

2 8

2 9

6 6

1 3

1 9

7 8

6 10

2 7

1 2

Output

667891964

31641898

769678014

1

29992112

654285930

776096678

444042335

886182048

728170986