SMALLEST MULTIPLE IN PERMUTED DIGITS | Code vita 2017

Problem Description:

Given two integers N, d , find the smallest number that is a multiple of d that could be formed by permuting the digits of N. You must use all the digits of N, and if the smallest multiple of d has leading zeros, they can be dropped. If no such number exists, output -1.

Input

A line containing two space separated integers, representing N and d.

Output

A single line giving the permutation of N that is the smallest multiple of d, without any leading zeroes, if any. If not such permutation exists, the output should be -1

Constraints

1≤N≤1000000000000
1≤d≤1000000

Example 1

Input

210
2

Output

12

Example 2

Input

1707693158
853684

Output
513917768

Example 3

Input

531
2

Output

-1

Explanation

1. In first test case the minimum number formed using all the three digits divisible by the given divisor is 012 which is equivalent to 12 and this is a multiple of d = 2. Hence the output is 12.
2. In second test case the minimum number formed using all the digits divisible by the given divisor is 0513917768. So in this case the output will be 513917768.
3. In the last case all permutations of digits of N are odd and hence not divisible by d.

SORTING BOXES | Code vita 2018

Problem Description

The parcel section of the Head Post Office is in a mess. The parcels that need to be loaded to the vans have been lined up in a row in an arbitrary order of weights. The Head Post Master wants them to be sorted in the increasing order of the weights of the parcels, with one exception. He wants the heaviest (and presumably the most valuable) parcel kept nearest his office.

You and your friend try to sort these boxes and you decide to sort them by interchanging two boxes at a time. Such an interchange needs effort equals to the product of the weights of the two boxes.

The objective is to reposition the boxes as required with minimum effort.

Constraints

N<=50

Weights <= 1000

Input Format

The first line consists of two space separated positive integers giving the number of boxes (N) and the position of the Head Post Master's office (k) where the heaviest box must be.

The second line consists of N space separated positive integers giving the weights of the boxes. You may assume that no two weights are equal.

Output

The output is one line giving the total effort taken to get the boxes in sorted order, and the heaviest in position k.

Explanation

Example 1

Input

5 2

20 50 30 80 70

Output

3600

Explanation

There are 5 boxes (N=5) and the heaviest box must be in position 2 (k=2). If we look at the final order (sorted, with the heaviest at position 2), it should be 20 80 30 50 70. If we look at this, we notice that only the 50 and the 80 parcels need to be exchanged. As this takes effort of the product of the weights, the effort is 4000.

Further reduction can be obtained if we use the smallest package (20) as an intermediary. If we exchange 20 with 50 (effort 1000), then with 80 (effort 1600) and back with 50 again (effort 1000), the effect is the same, with a total effort of 3600 (less th an the effort obtained by the direct move)an the effort

The results after the optimal sequence of exchanges are

50 20 30 80 70

50 80 30 20 70

20 80 30 50 70

As this takes an effort of 3600, the output is 3600.

Example 2

Input

6 3

30 20 40 80 70 60

Output

7600

Explanation

There are 6 parcels, and the heaviest should be at position 3. Hence the final order needs to be 20 30 80 40 60 70. If we look at the initial position, we see that 20 and 30 need to be exchanged (effort 600), 40 and 80 need to be exchanged (effort 3200) and 60 and 70 need to be exchanged (effort 4200). Hence the total effort is 600+3200+4200=8000.

If we use the same approach as in Example 1, we get the following efforts

(600) 20 30 40 80 70 60

(3200) 20 30 80 40 70 60

(1200) 60 30 80 40 70 20

(1400) 60 30 80 40 20 70

(1200) 20 30 80 40 60 70

A total effort of 7600 is obtained rather than an effort of 8000, which is the output.

HOP GAME | Code vita 2018

Problem Description

Dr Felix Kline, the Math teacher at Gauss School introduced the following game to teach his students problem solving. He places a series of “hopping stones” (pieces of paper) in a line with points (a positive number) marked on each of the stones.

Students start from one end and hop to the other end. One can step on a stone and add the number on the stone to their cumulative score or jump over a stone and land on the next stone. In this case, they get twice the points marked on the stone they land but do not get the points marked on the stone they jumped over.

At most once in the journey, the student is allowed (if they choose) to do a double jump that is, they jump over two consecutive stones - where they would get three times the points of the stone they land on, but not the points of the stone they jump over.

The teacher expected his students to do some thinking and come up with a plan to get the maximum score possible. Given the numbers on the sequence of stones, write a program to determine the maximum score possible.

Constraints

The number of stones in the sequence< 30

Input Format

The first line contains N, the number of integers (this is a positive integer)

The next line contains the N points (each a positive integer) separated by commas. These are the points on the stones in the order the stones are placed.

Output

One integer representing the maximum score

Explanation

Example 1

Input

3

4,2,3

Output

10

Explanation

There are 3 stones (N=3), and the points (in the order laid out) are 4,2 and 3 respectively.

If we step on the first stone and skip the second to get 4 + 2 x 3 = 10. A double jump to the third stone will get only 9. Hence the result is 10, and the double jump is not used

Example 2

Input

6

4,5,6,7,4,5

Output

35

Explanation

N=6, and the sequence of points is given.One way of getting 35 is to start with a double jump to stone 3 (3 x 6=18), go to stone 4 (7) and jump to stone 6 (10 points) for a total of 35. The double jump was used only once, and the result is 35.

GEMS COLLECTOR | Code vita 2018

Problem Description

Gems Collection is very interesting game. Given N sacks, each filled with random number of Gems, the objective of the game is to collect maximum number of Gems by picking up the sacks, subject to certain rules.

The rules are as follows

1. Start from left-most sack and move towards right. Player needs to decide then and there whether the current sack is to be picked up or not. Player cannot pick up sacks on the left once the player has moved past them.

2. Player cannot pick two consecutive sacks i.e. if the player picks Si then Si+1 can not be picked

3. The player can skip any number of sacks as desired

4. For every three consecutive skips, the player will get one Super Card.

5. The player can use one super card to pick two consecutive sacks one time

Example:

Gems in sacks: 5 8 12 3 6

Possible pickups without using Super Card: (5 and 12 and 6), (5 and 12), (5 and 3), (5 and 6), (8 and 3), (8 and 6), (12 and 6), only 5, only 8, only 12, only 3 and only 6

A Super Card allows the following pickup -

If Player skips sacks worth 5, 8 and 12 gems then player can pick-up consecutive sacks 3 and 6.

Once a super card is used, its power is lost.

Write a program to determine the maximum number of gems that can be collected by the player as the number of gems in all sacks is already known.

Constraints

1 <= T <= 10

1<= N <= 500

1 <= Gems in one sack <= 100

Input Format

The First line contains one integer T denoting the test cases.

For each test case,

the first line contains one integer N denoting number of sacks.

the second line contains N space delimited integers, representing the number of gems in each sack.

Output

Maximum number of gems for each test case T separated by new line.

Explanation

Example 1

Input:

1

3

7 10 1

Output:

10

Explanation

After applying all 5 rules, player can pick up maximum 10 gems.

Example 2

Input:

3

1

98

6

2 2 2 5 6 7

4

7 8 9 10

Output:

98

18

18

Explanation

For test case 1:

After applying all 5 rules, player can pick up maximum 98 gems as there is only one sack.

For test case 2:

Player will skip first three sacks to gain 1 super card and pickup 5 gems sack, then player will use super card to pick up 6 and 7 gems sack.

So, total gems = 5 + 6 + 7 = 18 gems.

For test case 3:

Player will pick 8 and 10 gems.

FARMING FIGURES | Code vita 2018

Problem Description

You are given N sticks of varying lengths. You need to determine whether it is possible to form a polygon of positive area by arranging them in some order. For example, if three sticks of lengths 1, 1, 1 are given we can easily see that we can form a triangle by arranging them in order. On the other hand, if the sticks have lengths 1, 2, 1, then we cannot form a polygon of non-zero area with these.

Constraints

1 <= N <= 100

Length of any stick will be less than 100

Input Format

The first line contains an integer N indicating number of sticks

The next line contains N space separated positive integers giving the lengths of the sticks

Output Format

One line containing the number of sides of the polygon of most sides (of at least 3 sides) that can be formed with some of the sticks. If no polygon can be formed, the output should be 0.

Explanation

Example 1

Input

3

1 1 1

Output

3

Explanation

N=3, and there are 3 sticks, each of length 1. With three sticks of length 1, we can form a triangle

Example 2

Input

4

1 2 3 6

Output

0

Explanation

We cannot form a 4 sided polygon using all four sticks. Similarly, a triangle cannot be formed with any three sticks. Since no polygon can be formed, the result is 0.

MIN PRODUCT ARRAY | Code vita 2016

Problem Description:

The task is to find the minimum sum of Products of two arrays of the same size, given that k modifications are allowed on the first array. In each modification, one array element of the first array can either be increased or decreased by 2.

Note- the product sum is Summation (A[i]*B[i]) for all i from 1 to n where n is the size of both arrays

Input Format: 

First line of the input contains n and k delimited by whitespace

Second line contains the Array A (modifiable array) with its values delimited by spaces

Third line contains the Array B (non-modifiable array) with its values delimited by spaces

Output Format:

Output the minimum sum of products of the two arrays

Constraints:

1 ≤ N ≤ 10^5

0 ≤ |A[i]|, |B[i]| ≤ 10^5

0 ≤ K ≤ 10^9

Sample Input and Output

S.No	Input	Output
1	3 5 1 2 -3 -2 3 -5	-31
2	5 3 2 3 4 5 4 3 4 2 3 2	25

Explanation for sample 1:

Here total numbers are 3 and total modifications allowed are 5. So we modified A[2], which is -3 and increased it by 10 (as 5 modifications are allowed). Now final sum will be
(1 * -2) + (2 * 3) + (7 * -5)
-2 + 6 - 35
-31

-31 is our final answer.

Explanation for sample 2:

Here total numbers are 5 and total modifications allowed are 3. So we modified A[1], which is 3 and decreased it by 6 (as 3 modifications are allowed).
Now final sum will be
(2 * 3) + (-3 * 4) + (4 * 2) + (5 * 3) + (4 * 2)
6 - 12 + 8 + 15 + 8
25

25 is our final answer. 

CONSECUTIVE PRIME SUM | Code vita 2016

Problem Description:

Some prime numbers can be expressed as Sum of other consecutive prime numbers.

For example

5 = 2 + 3
17 = 2 + 3 + 5 + 7
41 = 2 + 3 + 5 + 7 + 11 + 13

Your task is to find out how many prime numbers which satisfy this property are present in the range 3 to N subject to a constraint that summation should always start with number 2.
Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.

Input Format:

First line contains a number N

Output Format:

Print the total number of all such prime numbers which are less than or equal to N.

Sample Input and Output

SNo.	Input	Output	Comment
1	20	2	(Below 20, there are 2 such numbers: 5 and 17). 5 = 2 + 3 17 = 2 + 3 + 5 + 7
2	15	1	5 = 2 + 3

DATE AND TIME | Code vita 2018

Problem Description

Arun and his sister Usha are challenging each other with some mathematical puzzles. Usha, the cleverer one, has come up with the idea of givingArun 12 distinct digits from 0 to 9, and have him form the largest date time in 2018 with them. Arun is a little nervous, and asks you to help him with a computer program.

Usha will give Arun 12 distinct digits. He needs to create a date time combination in the year 2018: the date in the MM/DD form (all four digits must be present), and the time in the format HH:MM (all four digits must be present). The date may be from 01/01 to 12/31 and the time may be from 00:00 to 23:59 (in the 24 hour format). The digits provided may be used only once in the answer that Arun gives.

If more than one date time combination may be formed, Arun needs to give the latest valid date time possible in the year 2018.

Constraints

Single digits (any of 0-9)

Input Format

A line consisting of a sequence of 12 (not necessarily distinct) single digits (any of 0-9) separated by commas. The sequence will be non-decreasing.

Output

The maximum possible valid date time in the year 2018. The output must be in the format

MM/DD HH:MM

If no date time can be constructed, the output should be 0

Explanation

Example1 :

Input

0,0,1,2,2,2,3,5,9,9,9,9

Output

12/30 22:59

Explanation

The 12 digits to be used by Arun are given.

The maximum valid date time using only the digits given, and with each digit used at most once is

12/30 22:59

This is the output.

Example 2

Input

3,3,3,3,3,3,3,3,3,3,3,3

Output

0

Explanation

As no digit less than 3 is present in the input, a valid month cannot be formed. Hence no valid Date time can be formed with the input digits.

CROSS WORDS | Code vita 2018

Problem Description

A crossword puzzle is a square grid with black and blank squares, containing clue numbers (according to a set of rules) on some of the squares. The puzzle is solved by obtaining the solutions to a set of clues corresponding to the clue numbers.

The solved puzzle has one letter in each of the blank square, which represent a sequence of letters (consisting of one or more words in English or occasionally other languages) running along the rows (called “Across”, or “A”) or along the columns (called “Down” or “D”). Each numbered square is the beginning of an Across solution or a Down solution. Some of the across and down solutions will intersect at a blank square, and if the solutions are consistent, both of them will have the same letter at the intersecting square.

In this problem, you will be given the specifications of the grid, and the solutions in some random order. The problem is to number the grid appropriately, and associate the answers consistently with the clue numbers on the grid, both as Across solutions and as Down solutions, so that the intersecting blank squares have the same letter in both solutions.

Rules for Clue Numbering

The clue numbers are given sequentially going row wise (Row 1 first, and then row2 and so on)

Only blank squares are given a clue number

A blank square is given a clue number if either of the following conditions exist (only one number is given even if both the conditions are satisfied)

It has a blank square to its right, and it has no blank square to its left (it has a black square to its left, or it is in the first column). This is the beginning of an Across solution with that number

It has a blank square below it, and no blank square above it (it has a black square above it or it is in the first row). This is the beginning of a Down solution with that number

Constraints

5<=N<=15

5<=M<=50

Input Format

The input consists of two parts, the grid part and the solution part

The first line of the grid part consists of a number, N, the size of the grid (the overall grid is N x N) squares. The next N lines correspond to the N rows of the grid. Each line is comma separated, and has number of pairs of numbers, the first giving the position (column) of the beginning of a black square block, and the next giving the length of the block. If there are no black squares in a row, the pair “0,0” will be specified. For example, if a line contains “2,3,7,1,14,2”, columns 2,3,4 (a block of 3 starting with 2), 7 (a block of 1 starting with 7) and 14,15 (a block of 2 starting with 14) are black in the corresponding row.

The solution part of the input appears after the grid part. The first line of the solution part contains M, the number of solutions. The M subsequent lines consist of a sequence of letters corresponding to a solution for one of the Across and Down clues. All solutions will be in upper case (Capital letters)

Output

The output is a set of M comma separated lines. Each line corresponds to a solution, and consists of three parts, the clue number, the letter A or D (corresponding to Across or Down) and the solution in to that clue (in upper case)

The output must be in increasing clue number order. Ifa clue number has both an Across and a Down solution, they must come in separate lines, with the Across solution coming before the Down solution.

Explanation

Example 1

Input

5
5,1
1,1,3,1,5,1
0,0
1,1,3,1,5,1
1,1
5
EVEN
ACNE
CALVE
PLEAS
EVADE

Output

1,A,ACNE

2,D,CALVE

3,D,EVADE

4,A,PLEAS

5,A,EVEN

Explanation

N is 5, and the disposition of the black squares are given in the next 5 (N) lines. The grid looks like this

BRIDE HUNTING | Code vita 2018

Problem Description

Sam is an eligible bachelor. He decides to settle down in life and start a family. He goes bride hunting.

He wants to marry a girl who has at least one of the 8 qualities mentioned below:-

1) The girl should be rich.

2) The girl should be an Engineer/Doctor.

3) The girl should be beautiful.

4) The girl should be of height 5.3".

5) The girl should be working in an MNC.

6) The girl should be an extrovert.

7) The girl should not have spectacles.

8) The girl should be kind and honest.

He is in search of a bride who has some or all of the 8 qualities mentioned above. On bride hunting, he may find more than one contenders to be his wife.

In that case, he wants to choose a girl whose house is closest to his house. Find a bride for Sam who has maximum qualities. If in case, there are more than one contenders who are at equal distance from Sam’'s house; then

print "“Polygamy not allowed”".

In case there is no suitable girl who fits the criteria then print “"No suitable girl found"”

Given a Matrix N*M, Sam's house is at (1, 1). It is denoted by 1. In the same matrix, the location of a marriageable Girl is also denoted by 1. Hence 1 at location (1, 1) should not be considered as the location of a marriageable Girl’s location.

The qualities of that girl, as per Sam’'s criteria, have to be decoded from the number of non-zero neighbors (max 8-way) she has. Similar to the condition above, 1 at location (1, 1) should not be considered as the quality of a Girl. See Example section to get a better understanding.

Find Sam, a suitable Bride and print the row and column of the bride, and find out the number of qualities that the Bride possesses.

NOTE: - Distance is calculated in number of hops in any direction i.e. (Left, Right, Up, Down and Diagonal)

Constraints

2 <= N,M <= 10^2

Input Format

First Line contains the row (N) and column (M) of the houses.

Next N lines contain the data about girls and their qualities.

Output

It will contain the row and column of the bride, and the number of qualities that Bride possess separated by a colon (i.e. :).

Explanation

Example 1

Input:

2 9

1 0 1 1 0 1 1 1 1

0 0 0 1 0 1 0 0 1

Output:

1:7:3

Explanation:

The girl and qualities are present at (1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,4),(2,6),(2,9).

The girl present at (1,3) has 2 qualities (i.e. (1,4)and (2,4)).

The girl present at (1,4) has 2 qualities.

The Bride present at (1,6) has 2 qualities.

The Bride present at (1,7) has 3 qualities.

The Bride present at (1,8) has 3 qualities.

The Bride present at (1,9) has 2 qualities.

The Bride present at (2,4) has 2 qualities.

The Bride present at (2,6) has 2 qualities.

The Bride present at (2,9) has 2 qualities.

As we see, there are two contenders who have maximum qualities, one is at (1,7) and another at (1,8).

The girl who is closest to Sam's house is at (1,7). Hence, she is the bride.

Hence, the output will be 1:7:3.

Example 2

Input:

6 6

1 0 0 0 0 0

0 0 0 0 0 0

0 0 1 1 1 0

0 0 1 1 1 0

0 0 1 1 1 0

0 0 0 0 0 0

Output:

4:4:8

Explanation:

The bride and qualities are present at (3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)

The Bride present at (3,3) has 3 qualities (i.e. (3,4),(4,3) and (4,4)).

The Bride present at (3,4) has 5 qualities.

The Bride present at (3,5) has 3 qualities.

The Bride present at (4,3) has 5 qualities.

The Bride present at (4,4) has 8 qualities.

The Bride present at (4,5) has 5 qualities.

The Bride present at (5,3) has 3 qualities.

The Bride present at (5,4) has 5 qualities.

The Bride present at (5,5) has 3 qualities.

As we see, the girl present in (4,4) has maximum number of Qualities. Hence, she is the bride.

Hence, the output will be 4:4:8.