2.0 years ago

kb • 10

Question 1 of 3 :

High Jumping

We got the news that someone was jumping on the positive integer line holding a bag of gold coins. While jumping, he always dropped a gold coin at each position from the start to the end of his jump. We can visit only an integer place and collect the gold coins at that position.

Find the smallest position with the maximum number of coins.

Function Description

In the provided code snippet , implement the provided highjump (…) method to find the smallest position with the maximum number of gold coins. You can write your code in the space below the phrase "WRITE YOUR LOGIC HERE".

There will be multiple test cases running so the Input and Output should match exactly as provided. The base Output variable result is set to a default value of -404 which can be modified. Additionally, you can add or remove these Output variables.

Question 2 of 3 :

Maximum String Combinations

There are N dishes in a party named with different alphabets kept on the table given by a string S. Your friend has bought a combination of dishes donated by string D on his plate and you want the same combination of dishes for you as well. But you can choose only dishes that are kept consecutively to each other .You can also remove some dishes from the table. Suppose you remove X dishes from the table and the new set of dishes left on the table is string Q.

Find the Maximum number of non-overlapping combinations of dishes some as stringDthat can be found in stringQ, for all values ofXfrom0toN.

Function Description :

In the provided code snippet, Implement the provided maxstring (…) method to find the maximum number of non-overlapping combinations of dishes same as string D that can be found in string Q, for all values of X from 0 to N. You can write your code on the space below the phrase "WRITE YOUR LOGIC HERE".

Question 3 of 3

Find the Array

There is an integer array A of length N and the sum of the elements of array is X. You are given an integer array B of length N, which is given as B [i] = X - A [i], for all 0 <= i <= N - 1.

Find the array A.

Note: For a given array B[i] , there will always be an array A [i]

Function Description :

In the provided code snippet, implement the provided "findarray(...)" method to find A. You can write your code in the space below the phrase "WRITE YOUR LOGIC HERE".

There will be multiple test cases running so the Input and the Output should match exactly as provided. The base output variable result is set to a default value of -404 which can be modified. Additionally, you can add or remove these output variables.

11 months ago

Manas 310

Bānswāra

Question 1

• Solution : We are given an array of starting and ending positions of the jumps. For all jumps one gold coin is added to all numbers between the starting and the ending positions. Since we need to find the smallest position where the number of coins are maximum, it will be the starting point of some jump. Let's discuss following algorithm to solve the problem.
• Add all the starting positions and ending positions to an array (Add each element as a pair {x,1} denotes starting and {y+1,-1) denotes the ending at point y)
• We add the value of ending + 1 to the array since all values between start to end (include) will have 1 gold coin added.
• Sort the array.
• If we take the prefix sum of the elements of the array (second element of each pair), then the position with the maximum value will be our answer. 1 is added to all the position between some st[i] and end[i] and we have position end + 1 with value -1, which makes the sum as 0 for that start, end pair.
• Taking the start position with the maximum value after the prefix sum will give us the answer.
• Complexity will be O(N)

Below is the pseudo code:

int val = 1;
int position  = v[0].first;
sort(v.begin(),v.end());
for(int i = 1; i < 2*n;i++)
{
    v[i].second += v[i-1].second;
    if(v[i].second > val)
    {
        val = v[i].second;
        position = v[i].first;
    }
}

4 months ago

Ujjwal Srivastava 320

Bengaluru

Question 3

Overview

• Given an integer array A of length N and the sum of the elements of this array is X.
• You are given an integer array B of length N which is given as B[i] = X - A[i] for all 0<=i<=N-1.
• We have to find Array A.

Solution

• We just have to find the value of X, then every element A[i] will be equal to X-B[i].
• We know that sum of Array B will be N*X-(A[0]+A[1]+...+A[N-1]). Let us name this SumB.
• Now given (A[0] +A[1]+....+A[N-1]) = X.
• So by the above two points N*X-X = SumB which implies X=(SumB)/(N-1). Hence every element can be founded by point 1.