Programming & Computer Science Answers

Rearrange Numbers in String

Given a string, write a program to re-arrange all the numbers appearing in the string in decreasing order. Note: There will not be any negative numbers or numbers with decimal part.

Input

The input will be a single line containing a string.

Output

The output should be a single line containing the modified string with all the numbers in string re-ordered in decreasing order.

Explanation

For example, if the given string is "I am 5 years and 11 months old", the numbers are 5, 11. Your code should print the sentence after re-ordering the numbers as "I am 11 years and 5 months old".

Sample Input 
I am 5 years and 11 months old
Sample Output 
I am 11 years and 5 months old

Vowel Sound

Given a sentence, write a program rotate all the words left, so that every word starts with a vowel.
Note: If there is no vowel in the word, do not rotate it.

Input

The input will be a single line containing a string.

Output

The output should be a single line containing the modified sentence with rotated words.

Explanation

For example, if the given string is "I saw a DRAGON flying in the sky", rotating each word towards left in this way "I aws a AGONDR and ingfly in eth sky", makes every word start with a vowel letter. The word "sky" is not rotated as it does not have any vowel in it. The words "I", "a", "and", "in" are not rotated as they already start with a vowel.

Sample Input 
I saw a DRAGON flying in the sky
Sample Output 
I aws a AGONDR ingfly in eth sky

Matrix Diagonal Sum

Given a square matrix, print the sum all diagonal elements of the matrix.

Input

The first line of input will be an integer N, denoting the no. of rows in the matrix. The following N lines will contain space-separated integers denoting the elements of each row of the matrix.

Output

The output should be a single integer denoting the sum of all the diagonal elements.

Explanation

For example, if the given N is 3, and the given matrix is
1 2 3
4 5 6
7 8 9
The diagonal and anti-diagonal elements of the above matrix are 1, 3, 5, 7, 9. So the output should be 25

Sample Input 
3
1 2 3
4 5 6
7 8 9
Sample Output 
25

Repeating & Non-Repeating Numbers

Given a list of numbers, find and print, the first number that occurs only once in the list and the first number that occurs more than once in the list.

Input

The input will be a single line containing space-separated integers.

Output

The first line of the output should contain the first non-repeating number. The second line of output should contain first repeating number. If there is no number fitting the given criteria, print "None" instead.

Explanation

For example, if the given list of integers are 5, 5, 4, 7, 4, 1, 11 , the first non-repeating number is 7 and the first repeating number is 5.

Sample Input 1
5 5 4 7 4 1 11
Sample Output 1
7
5

Sample Input 2
1 2 3 4 5 6 7 8 9
Sample Output 2
1
None

Area of Largest Rectangle in Histogram

Given an list of integer 

heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input

The input will be a single line containing space-separated integers, denoting the heights of the bars.

Output

The output should be a single line containing the area of the largest rectangle in the rectangle.

Explanation

For example, if the given list of numbers are 

2 1 5 6 2 3 , when they are drawn adjacent to each other according to their heights, the histogram will be like

The largest rectangle can be found in between 5 and 6, which is 10.

Sample Input 1
2 1 5 6 2 3
Sample Output 1
10

Sample Input 2
65 87 96 31 32 86 57 69 20 42
Sample Output 2
248

Palindrome Pairs

Given a list of unique words, write a program to print all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of two words at indices i and j is a palindrome.

Input

The input will be a single line containing a sentence.

Output

The output should be printing each distinct pair of indices (i, j) each in a line in ascending order.
If there are no distinct pairs found, print "-1"
Note: Consider (i, j) and (j, i) as two different pairs.

Explanation

For example, if the given sentence is

was it a car or a cat I saw

The words that can be concatenated to make a palindrome are

Words	Indices
(was, saw)	(0, 8)
(a, a)	(2, 5)
(a, a)	(5, 2)
(saw, was)	(8, 0)

So the output should be

0 8
2 5
5 2
8 0
Sample Input 1
was it a car or a cat I saw
Sample Output 1
0 8
2 5
5 2
8 0

Sample Input 2
bat tac tab cat
Sample Output 2
0 2
1 3
2 0
3 1