9 weeks ago

John 910

Hyderabad

Question 1

Suppose a=1, b=2,......, z=26. Given a string Str, which carries the number series. The task is to figure out all the ways to convert it into a letter series.

Example 1:

Input:

421 a Value of Str

Output:

2

Explanation:

Here, Str=421.

First possibility is 4 = d and 21 = u, so du.

Second possibility is 4 = d, 2 = b and 1 = a, so dba.

Hence the output is 2.

Note: Possibility of {42,1} will not take into consideration because 42 is greater than 26 and not valid digit for conversion.

Example 2:

Input:

101 a Value of Str

Output:

1

Question 2

Ria likes to play a number games always. Today she decided to find the largest number that can be made using all of the digits of the given input (Non-negative integer) value N.

Example 1:

Input

3675092 a Value of N

Output

9765320

Example 2:

Input:

02856 a Value of N

Output:

8652

Note: Since input value, N accepts integer value only, hence digit 0 that comes before the first nonzero digit should not taken into consideration of input.

Constraints

1 < N < 10000000

The Input format for testing

The candidate has to write the code to accept a positive integer number.

Question 3

Given a number N, the task is to split the Num into multiple parts in such a fashion as to find the highest product. Print the highest product value.

Consider N= 4.

Best: 4 = 2 + 2 and 2 * 2 = 4

Similarly for N = 6, (3*3) = 9

For N = 8, (233) = 18

For N = 15, (33333) = 243

Constraints:

1 <= N <= 100

Example 1

Input

4 a Value of N

Output

4

Example 2

Input

6 a Value of N

Output

9

Question 4

Given a non-negative integer array Arr having size N. Each element of the array will carry a different value. This means no two elements can have same values. the candidate has to do with minimal changes in the original value of elements, making every element as least as much as it originally had.

Find the minimum sum of all elements that can be set the array for.

Example 1:

Input

3 a Value of N, represents size of Arr

2 a Value of Arr[0]

2 a Value of Arr[1]

4 a Value of Arr[2]

Output

9

Explanation

As of two elements have the same value, max value for one of them needs to be incremented to 3.

He can set the array with 2+3+4=9.

Question 5

A group of friends are playing cards. Only numeric cards are in consideration along with the joker card(equivalent to 0) and the symbols in the cards are not taken into account. Each player will receive a set of cards. The rule of the game is to rearrange the set of cards to the possible lowest sequence. Player with the set of cards forming the smallest number wins the game. The sequence of cards should not start with a joker card. Task is to write a program for developing the logic of the game considering the set of cards as a number.

Example 1:

Input

3421 --- Value of CardSet

Output

1234 --- Prints the lowest number matching the set criteria

Explanation:

The lowest number formation by rearranging the digits of the number 3421 and not starting with a 0 will1234 Hence, the output is a '1234'.

Question 6

Aman is in a science lab and in today's experiment he is given a task to bring z ml of the starch solution into a test tube by his teammates. He is given three test tubes a, B and C of capacities x, y and N ml respectively, where (N=x+y). His task is to fill test tube C with z ml with the help of test tubes A and B from a large beaker.

Aman is not good at handling test tubes. While handling any test tube A or B, he either empties it or fully fills it but does not waste the starch solution while filling any test tube A or B. You can fill the test tubes A or B either from the beaker or from test tube C. Your task is to determine, will he be able to get z ml starch solution in test tube C or not.

Example 1:

Input

3 4 ---- Value of x and y respectively

2 ---- Value of z

Output

YES ---- Denotes whether Aman can get the required solution for experiment

Explanation:

He can first fill test tube by 6ml by filling A test tube two times, (3+3)=6

Then he can fill test tube B completely from test tube C once, (6-4)=2

2 ml remains in the test tube.

21 months ago

Yash Sahijwani 940

Solution to Question 4

Analysis

In the question, we are given an integer array consisting of only non-negative integers, and we can increase some elements (since each element should be greater than or equal to what it was originally) so that all elements of the array are unique, and they have their sum as low as possible.

The main idea for this would be to start from the smallest element in the array, and check its freq. If it has a frequency of 1, we move on to the next. Otherwise, apart from 1 occurrence of this element, for all other occurrences we add 1 to the element. This is done because the frequency of each element can only be 1. Now we move on to the next element, and add 1 to all occurrences except one of them. We keep on doing this till we get to the last element, so that each element has frequency equal to 1.

Now while implementing, finding all the occurrences of each element in the array can take O(n) time making the overall time complexity O(n^2) which is not desired. So we find another method to do this. We can keep a set, which consists of all the unique elements in the array currently, and a map which stores the frequency of all these elements. For the initial array, this can be done in O(nlogn) time.

Now we take the smallest element from the set, and check its frequency. If the number is say num and its frequency is greater than 1, say val, then we increase the frequency of num+1 by val-1 and decrease the frequency of num to 1. So now, num has frequency 1 and so it is unique. All other occurrences of num have been increased to num+1. We also add num+1 to the original set which consisted of all unique elements of the array if it is not present already. Now, for moving on to the next element, we binary search on the unique elements in the set, to find the next greater element present in the array. This can be implemented in C++ using upper_bound function. We end the loop when the upper bound gives us the end of the set.

Implementation

set < int > unique;
map < int, int > freq;
// Initialize unique and freq
int curr = smallest_element - 1;
while(true)
{
    auto it = unique.upper_bound(curr);
    if(it==unique.end())
        break;
    int val = *it;
    if(freq[val]==1)
    {   
        curr = val;
        continue;
    }
    freq[val+1] += (freq[val]-1);
    unique.insert(val+1);
    curr = val;
}

8 months ago

Akshay Sharma 990

Chandigarh

Question 2

Overview

• We are given an integer N that contains digits from 0-9.
• We need to form a new Number N` that is the largest possible number.
• We need to find the optimal way to solve this problem that can be also solved in higher constraints

Solution

• Before going to any approach we much take care that if we are given a number that contains the preceding 0 before any other digits are not to be included in the answer. Why ? As the reason is quite simple we are given an integer and a number of zeros before any number doesn't count .-
• So we can run a while loop and iterate over it till we didn't get the first digit as Non-Zero and Update the starting index of our string at that point.
• The simple approach that may everyone thinks of is to take the given input as a string and sort the given string after removing front zeros and return the string but have u thought about its time complexity? It's really horrible that is O(NlogN) that may interview needed from you.
• The best approach we can follow up is that we know that the only digits that are included in any Number range from 0 to 9.
• So the idea is to create hashed array or freq array of size 10 and store the count of every digit that occurs in that number.
• Then traverse the hashed array from index 9 to 0 and check if the count of i th index is 0 or not and calculate the number accordingly and store that number in form of a string or use some maths.
• Time complexity : O(N)

8 months ago

Akshay Sharma 990

Chandigarh

Question 3

Overview

• We are given a number N that is less than 100
• We need to break that number N such that the product of those broken numbers is the highest.
• For eg, if we are given the number 4 we can break it like (2,2)(1,1,1,1)(1,3)(2,1,1) so that such sum of the broken number is N and the product we get is maximised in the above case highest product we are getting is by the pair (2,2).
• Mathematically, we are given n and we need to maximize a1 * a2 * a3 …. * aK such that n = a1 + a2 + a3 … + aK and a1, a2, … ak > 0.
• We need to return the highest product value for that given Number N.
• Note that we need to break the given Integer N into at least two parts in this problem for maximizing the product.

PreRequiste

• Maxima and minima concept

Solution

• The solution we can use is that if an integer needs to break into two parts, then to maximize its product those parts should be equal.
• So using this concept let's break n into (n/k) k’s then their product will be k(n/k), now if we take the derivative of this product and make that equal to 0 for maxima, we will get to know that value of k should be e (base of the natural logarithm) for the maximum product.
• As we know that 2 < e < 3, so we should break every Integer into 2 or 3 only for the maximum product.
• Next thing is 6 = 3 + 3 = 2 + 2 + 2, but 3 * 3 > 2 * 2 * 2, that is every triplet of 2 can be replaced with a tuple of 3 for the maximum product,
• So we will keep breaking the number in terms of 3 only until the number remains as 4 or 2, which we will be broken into 2*2 (2*2 > 3*1) and 2 respectively and we will get our maximum product.
  • We can easily implement the above statement using recursion and switch statements.
  • The cases for the switch statement can be If N is completely divided by 3 then we can divide our number in the break of 3s only as we are getting maximum product than only.
  • If dividing N with 3 gives 1 as the remainder then we can break the number by 4 + all other 3.
  • if dividing N with 3 gives 2 as the remainder then we can break 2 + all other 3
  • So we try to break the integer in the power of 3 only and when the integer remains small (<5) then we can easily use brute force to find a solution.
  • Time Complexity: O(LogN)

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Problem 1

Analysis

We can solve the given problem by using dynamic programming. Let dp[i] denote the number of ways of decoding the prefix of length i of the given string. Now, we have two choices :

• either the ith character alone gets mapped to a valid character and thus our problem reduces to finding the number of ways to decode the prefix of length i-1.
• The i-1th and ith characters combined map to a valid character and thus our problem reduces to finding the number of ways to decode the prefix of length i-2.

Hence, by using the above transitions, we can find the number of ways of decoding the entire string, i.e. dp[n] in O(N).

Implementation

We can implement the given dynamic programming either using tabulation or memoization. The pseudoCode below implements the solution using memoization.

PseudoCode

valid(T):                                        //helper function that returns true if the given string is a valid character code and false otherwise.
    if(T[0] == '0' or int(T) > 26):      
        return false
    return true

solve(S,index):
    if(index<0):                                 //base case, if we have 0 characters there is exactly one way to decode it 
        return 1
    if(dp[index]!=-1):                           //If we have already calculated the ans for this index, we return it
        return dp[index]
    if(valid(S[index])):
        dp[index] = solve(S,index-1)             // Calculating the dp for this prefix using the transitions explained. 
    if(valid(S[index-1:index])):
        dp[index] += solve(S,index-2)

8 months ago

Banavathu. Lakshmi • 10

Hyderabad

n=int(input())
arr=list(map(int,input().split()))
arr.sort()
for i in range(1,n):
    if arr[i]<=arr[i-1]:
        arr[i]=arr[i-1]+1 
    else:
        pass
print(sum(arr))