DISTRIBUTE BOOKS | Code vita 2019

Problem Description 

For enhancing the book reading, school distributed story books to students as part of the Children’s day celebrations.
To increase the reading habit, the class teacher decided to exchange the books every weeks so that everyone will have a different book to read. She wants to know how many possible exchanges are possible.
If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-th student and after the exchange he should get a different book, other than Bi.

B1 B2 B3 B4 - first state, before exchange of the books
B2 B1 B4 B3
B2 B3 B4 B1
B2 B4 B1 B3
B3 B1 B4 B2
B3 B4 B1 B2
B3 B4 B2 B1
B4 B1 B2 B3
B4 B3 B1 B2
B4 B3 B2 B1

Find the number of possible exchanges, if the books are exchanged so that every student will receive a different book.

Constraints 

1<= N <= 1000000

Input Format 

Input contains one line with N, indicates the number of books and number of students.

Output 

Output the answer modulo 1000000007.

Example 1

Input

4

Output

9

GROOVING MONKEYS | Code via

Problem Description

N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.

The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.

Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.

This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing at the ith position.

Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.

Constraints

1<=t<=10 (test cases)

1<=N<=10000 (Number of monkeys)

Input Format

First line contains single integer t, denoting the number of test cases.

Each test case is as follows -

Integer N denoting the number of monkeys.

Next line contains N integer denoting the dancing pattern array, monkeys[].

Output

t lines,

Each line must contain a single integer T, where T is the minimum number of seconds after which all the monkeys are in their initial position.

Example 1

Input

1

6

3 6 5 4 1 2

Output

6

Explanation

Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.

Suppose monkeys are a,b,c,d,e,f, & Initial position (at t = 0) -> a,b,c,d,e,f

At t = 1 -> e,f,a,d,c,b

a will move to 3rd position, b will move to 6th position, c will move to 5th position, d will move to 4th position, e will move to 1st position and f will move to 2nd position. Thus from a,b,c,d,e,f at t =0, we get e,f,a,d,c,b at t =1. Recursively applying same transpositions, we get following positions for different values of t.

At t = 2 -> c,b,e,d,a,f

At t = 3 -> a,f,c,d,e,b

At t = 4 -> e,b,a,d,c,f

At t = 5 -> c,f,e,d,a,b

At t = 6 -> a,b,c,d,e,f

Since at t = 6, we got the original position, therefore the answer is 6.

BALANCING STARS | CODE VITA 2019

Problem Description

CODU loves to play with string of brackets.

He considers string as a good string if it is balanced with stars. A string is considered as balanced with stars if string contains balanced brackets and between every pair of bracket i.e. between opening and closing brackets, there are at least 2 stars(*) present. CODU knows how to check whether a string is balanced or not but this time he needs to keep a track of stars too. He decided to write a program to check whether a string is good or not. But CODU is not as good in programming as you are, so he decided to take help from you. Will you help him for this task? You need to print Yes and number of balanced pair if string satisfies following conditions(string is good if it satisfies following 2 conditions):

1. The string is balanced with respect to all brackets.

2. Between every pair of bracket there is at least two stars.

However if string doesn't satisfies above conditions then print No and number of balanced pair in string as an output.

Constraints

4 <= String length <= 1000

Input Format

The first and only line of input contains a string of characters(a-z,A-Z), numbers(0-9), brackets( '{', '[', '(', ')', ']', '}' ) and stars(*).

Output

Print space separated "Yes" (without quotes) and number of balanced pair if string is good. Else print "No" (without quotes) and number of balanced pair.

Example 1

Input

{**}

Output

Yes 1

Explanation

Here string contains one balanced pair {} and between this pair of bracket there are 2 stars present so the output is Yes with the count of balanced pair as 1.

Example 2

Input

{**(**{**[**]})}

Output

Yes 4

Explanation

String has balanced brackets and also satisfies 2nd condition. So the output is Yes with count of balanced pair which is 4.

Example 3

Input

**}xasd[**]sda231

Output

No 1

Explanation

In this case string is not balanced. So the output is No with the count of balanced pair as 1.

NEW ATM DESIGN | CODE VITA 2019

Problem Description

Automated Teller Machine (ATM) is an electronic device that enables people to withdraw cash from their bank account. Every ATM has a limit for number of currency notes (say N), it can give at a time.

A bank wants to design an ATM for school students. The unique feature of this ATM would be that it would always give maximum number of currency notes possible, to make the students happy.  Available denomination of currency notes in the ATM are 100, 200, 500, 1000

Constraints

N<100

Input Format

First Line provides an integer, N

Second Line provides an integer denoting the amount you want to withdraw (in multiples of 100)

Third Line provides an integer denoting the available currency note of Rs 100 in the ATM

Fourth Line provides an integer denoting the available currency note of Rs 200 in the ATM

Fifth Line provides an integer denoting the available currency note of Rs 500 in the ATM

Sixth Line provides an integer denoting the available currency note of Rs 1000 in the ATM

Output

One line containing the maximum number of currency note possible for the desired withdrawal amount. Output should be 0 (zero) if transaction is not possible, for example if sufficient fund is not available in the ATM.

Example 1

Input

10

1300

10

10 

10

10

Output

10

Explanation

Here,

7 * 100 + 3* 200 + 0*500 +0*1000 hence maximum possible currency = 10. 

Example 2

Input

5

1700

1

2

2

2

Output

3

Explanation

Here,

0 * 100  + 1 * 200 + 1 * 500 +1 * 1000 hence maximum possible currency = 3.

EXCHANGE DIGITS | CODE VITA 2019

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.

Example 1

Input

459 500

Output

549

Example 2

Input

645757 457765

Output

465577

Example 3

Input

5964 9984

Output

-1

STRING ROTATION

Input:

rhdt:246, ghftd:1246

Output:

trhd, ftdgh

Explanation:

Here, every string (rhdt : 1246) is associated with a number, separated by semicolon, if sum of square of digit is even the rotate the string right by 1 position. If square of digit is odd the rotate the string left by 2 position.  

For first case: 

2*2+4*4+6*6=84 which is even so rotate string, rotate right by 1 so ”rhdt” will be “trhd”

For second case: 

1*1+2*2+4*4+6*6=85 which is odd so rotate string left by 2 so “ghftd” will be “ftdgh”

LONGEST SUBARRAY

One have to find the longest subarray such that its element satisfies the following condition:

  x[i]=x[i‐ 1]+x[i-2]   

If more than one subarray of is found of maximum length one has to print the array which starts with the minimum element and if they are also same then the array with minimum second element and so on.   If no subarray is found one has to print ‐1. 

Input:

3, 5, 8, 2, 19, 12, 7, 11

Output:

2, 5, 7, 12, 19

MATRIX WITH HIGHEST SUM

Take string input then form all possible mXm square matrix, and print the matrix with maximum sum. In case, two or more square matrix has maximum sum then print largest matrix followed by next largest matrix and so on. In case, more than one matrix has same size print in order of their occurrence.  

INPUT: 

6, 3, 6, 20, 3, 6,-15, 3, 3

OUTPUT:           

6 3 6         

20 3 6        

-15 3 3 

                 

6 3          

6 20                     

6 20          

3 6

Explanation:-  

6 3 6 

20 3 6 -> its sum is 35 and is order 3*3,

-15 3 3

6 3

6 20 -> its sum is 35 and is order 2*2,

6 20

3 6 -> its sum is 35 and is order 2*2,

SHELDON COOPER AND HIS BEVERAGE PARADIGM | Code vita 2015

Problem Description

Sheldon Cooper, Leonard Hofstadter and Penny decide to go for drinks at Cheese cake factory. Sheldon proposes to make a game out of this. Sheldon proposes as follows,

To decide the amount of beverage they plan to consume, say X.

Then order for a random number of different drinks, say {A, B, C, D, E, F} of quantities {a, b, c, d, e, f} respectively.

If quantity of any three drinks add up to X then we'll have it else we'll return the order. E.g. If a + d + f = X then True else False

You are given

Number of bottles N corresponding to different beverages and hence their sizes

Next N lines, contain a positive integer corresponding to the size of the beverage

Last line consists of an integer value, denoted by X above

Your task is to help find out if there can be any combination of three beverage sizes that can sum up to the quantity they intend to consume. If such a combination is possible print True else False

Input Format:

First line contains number of bottles ordered denoted by N

Next N lines, contains a positive integer Ai, the size of the ith bottle

Last line contains the quantity they intend to consume denoted by X in text above

Output Format: 

True, if combination is possible False, if combination is not possible

Constraints: 

N >= 3 Ai > 0 1 <= i <= N X > 0   

Example 1

Input:

6

1 4 45 6 10 8

22

Output:

True

Example 2

Input:

4

1 3 12 4

14

Output:

False

REVERSE GEAR | Code vita 2015

Problem Description

A futuristic company is building an autonomous car. The scientists at the company are training the car to perform Reverse parking. To park, the car needs to be able to move in backward as well as forward direction. The car is programmed to move backwards B meters and forwards again, say F meters, in a straight line. The car does this repeatedly until it is able to park or collides with other objects. The car covers 1 meter in T units of time. There is a wall after distance D from car's initial position in the backward direction.

The car is currently not without defects and hence often hits the wall. The scientists are devising a strategy to prevent this from happening. Your task is to help the scientists by providing them with exact information on amount of time available before the car hits the wall.

Input Format:

First line contains total number of test cases, denoted by N

Next N lines, contain a tuple containing 4 values delimited by space

F B T D, where

F denotes forward displacement in meters

B denotes backward displacement in meters

T denotes time taken to cover 1 meter

D denotes distance from Car's starting position and the wall in backward direction

Output Format:

For each test case print time taken by the Car to hit the wall

Constraints:

First move will always be in backward direction

1 <= N <= 100

backward displacement > forward displacement i.e. (B > F)

forward displacement (F) > 0

backward displacement (B) > 0

time (T) > 0

distance (D) > 0

All input values must be positive integers only

Example 1

Input:

2
6 9 3 18
3 7 5 20

Output:

162
220

SAVING FOR A RAINY DAY | Code vita 2015

Problem Description:

By nature, an average Indian believes in saving money. Some reports suggest that an average Indian manages to save approximately 30+% of his salary. Dhaniram is one such hard working fellow. With a view of future expenses, Dhaniram resolves to save a certain amount in order to meet his cash flow demands in the future. Consider the following example. Dhaniram wants to buy a TV. He needs to pay Rs 2000/- per month for 12 installments to own the TV. If let's say he gets 4% interest per annum on his savings bank account, then Dhaniram will need to deposit a certain amount in the bank today, such that he is able to withdraw Rs 2000/- per month for the next 12 months without requiring any additional deposits throughout. Your task is to find out how much Dhaniram should deposit today so that he gets assured cash flows for a fixed period in the future, given the rate of interest at which his money will grow during this period.

Input Format:

First line contains desired cash flow MSecond line contains period in months denoted by TThird line contains rate per annum R expressed in percentage at which deposited amount will grow

Output Format:

Print total amount of money to be deposited now rounded off to the nearest integer Constraints: M > 0 T > 0 R >= 0 Calculation should be done upto 11-digit precision 

Example 1

Input:

500

3

12

Output:

1470

Example 2

Input:

600

3

5.9

Output:

17824

Example 3

Input:

500

2

0

Output:

100