SDE - 1

You are given an array “ARR” of N integers. You are required to perform an operation on the array each time until it becomes empty. The operation is to select an element from the array(let’s say at ith index i.e ARR[i]) and remove one occurrence of the selected element from the array and remove all the occurrences of (ARR[i]-1) and (ARR[i]+1) from the array(if present). Your task is to maximize the sum of selected elements from the array.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5].

The maximum possible sum for the given array would be 14. Because if we select one of the 3’s from the array, then one 3 and all occurrences of (3-1) and (3+1) i.e 2 and 4 will be deleted from the array. Now we left with {3,3,5} elements in the array. Then again we select 3 in the next two steps and in both steps 3 will be deleted also (3-1) and (3+1) doesn't exist in the array so nothing extra to delete in both steps. Now we left with only {5} and in the next step, we select the 5 and delete it. Then the array becomes empty. Thus the sum of selected elements will be 3+3+3+5 = 14.

You are given an array/list 'NUM' of integers. You are supposed to rearrange the elements of the given 'NUM' so that after rearranging the given array/list there are no two adjacent elements present in the rearranged 'NUM' which will be the same.

For example:

Input: NUM[] = {1,1,1,2,2,2} 
Output: {1,2,1,2,1,2}
Note: {2,1,2,1,2,1} is also valid because there are no two adjacent which are the same.

Yogesh is a very intelligent student and is interested in research in Machine Learning domain. His college has only one professor, Mr. Peter working in that field. He approaches the professor for the same, but professor wants to test him first.

To pass the test Yogesh must answer Q questions correctly. In all the Q questions, professor gives him three positive integers : A, B and K where A ≤ B.

Now Yogesh has to find an integer P such that it is closest to integer A and there are at least K prime numbers in range [A, P], where A <= P <= B.

Help Yogesh to find and print minimum possible P or print -1 if there no such possible integer.

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

You are given a string 'str' of length 'N'.

Your task is to reverse the original string word by word.

There can be multiple spaces between two words and there can be leading or trailing spaces but in the output reversed string you need to put a single space between two words, and your reversed string should not contain leading or trailing spaces.

Example :

If the given input string is "Welcome to Coding Ninjas", then you should return "Ninjas Coding to Welcome" as the reversed string has only a single space between two words and there is no leading or trailing space.

You have been given an integer array/list (ARR) of size N. You have to return an array/list PRODUCT such that PRODUCT[i] is equal to the product of all the elements of ARR except ARR[i]

 Note :

Each product can cross the integer limits, so we should take modulo of the operation. 

Take MOD = 10^9 + 7 to always stay in the limits.

Follow up :

Can you try solving the problem in O(1) space?