9 weeks ago

John 910

Hyderabad

Question 1

Superhero

A superhero is having a strength of zero in the beginning. Two integer arrays are given both of length n. Each element of the array contains the strength a superhero can get if he takes that particular element. The superhero can choose one complete array and he can add the elements of the array to his strength.

Before he does this, he can also perform another operation to maximize his strength. He can choose two integers I and r where 0 <= 1 <= r < n and swap the subarray array[1.....r].

He can apply the mentioned operation once or not do anything, before choosing one complete array. Return the maximum strength he can get.

Input Format

Line 1 - an integer n.

Line 2 - n space separated integers of Array 1.

Line 3 - n space separated integers of Array 2.

Constraints

n == array1.length == array2.length

1<= n <= 10^5

1 <= array1[i], array2[i] <= 10000

Output Format

An integer

Sample Input 0

5
20 40 20 70 30
50 20 50 40 20

Sample Output 0

220

Explanation 0

Choosing left = 3, right = 4, we have array1 = [20,40,20,40,20] and array2 = [50,20,50,70,30]. The score is max(sum(nums1), sum(nums 2)) = max(140, 220) = 220.

![PhonePe 1.1][1] ![PhonePe 1.2][2]

Question 2

Naming the twins

One pair of twins are born in a village. The parents wanted to name the children and for this they went to the village leader. The leader suggested them to keep the names of the children such that the difference between the frequencies of each letter from 'a' to 'z' between the two names is at most 3. You will be given two names. If the two names satisfy the condition, print a single string "Possible". If the condition is not met, print "NotPossible".

Input Format

First line will contain a single integer t denoting the number of test cases.

First line of each test case will contain two space separated strings s1 and s2 denoting the name of the first child(name1) and second child(name2) respectively.

Constraints

1<= t <= 10

1 <= length of each name <= 100

Output Format

Print a single string.

Sample Input 0

2
abcdeef abaaacc 
aaaa bccb

Sample Output 0

Possible 
NotPossible

Explanation 0

Test case 1:

'a' appears 1 time in name1 and 4 times in name2. The difference is 3.

'b' appears 1 time in name1 and 1 time in name2. The difference is 0.

'c' appears 1 time in name1 and 2 times in name2. The difference is 1.

'd' appears 1 time in name1 and 0 times in name2. The difference is 1.

'e' appears 2 times in name1 and 0 times in name2. The difference is 2.

'f' appears 1 time in name1 and 0 times in name2. The difference is 1.

The maximum difference is 3 and thus the condition is satisfied.

Test case 2:

There are 4 'a's in "aaaa" but O 'a's in "bccb".

The difference is 4, which is more than the allowed 3.

Question 3

Max Frequency

Bob has an array of integers arr of size n and an integer x. Alice asks him to perform a few operations on the array.

In one operation Bob can choose any index and increment the element at that index by 1. He can perform at most x such operations.

Alice is curious and wants to know what could be the maximum occurrence of any element of array after performing at most x such operations.

Alex is too lazy to perform the task , can you help him find the answer so that he could impress Alice.

Input Format

First line contains integers n and x.

Second line contains n space separated integers.

Constraints

1 <= n <=10^5

1 <= arr[i] <= 10^5

1 <= x <=10^5

Output Format

Print the maximum occurrence of the element in the array.

Sample Input 0

4 5
1 4 8 13

Sample Output 0

2

Explanation 0

Optimal ways could be: increment the first element three times,arr = [4,4,8,13] or, increment the second element four times,arr = [1,8,8,13] or, increment the third element five times,arr = [1,4,13,13]. In all the above cases maximum possible occurrence of any element is 2.

Question 4

Aladdin positioned on (0, 0) wants to reach Jasmine at (r-1, c-1). He has k coins. We are given with a grid of cities where each city either charges 1 coin or 0 coins. Aladdin can move either horizontally or vertically one step in this grid to reach Jasmine. Find out the minimum steps taken to reach Jasmine.

Example:

r = 5, c = 3, k = 1

0 0 1
1 0 1
1 0 1
0 1 0
0 0 0

Ans:

6

Question 5

There is a grid of (10^18, 10^18) blocks. The person standing on (i, j) block can move to (2i, j) or (i, 2j) or (i-j, j) or(i, j-i) inside the grid. If he starts from (1, 1) output "Yes" if he/ she could reach (m, n) block else output "No"

Input:

t: No of m, n values

List of m, n values

Output:

t Yes or No

Example

Input:

3
1 2
4 7
10 10

Output:

Yes
Yes
No

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Question 1

Analysis

If we do not perform the mentioned operation, then the ans is max(sum(array1), sum(array2)).

Now, if we perform the operation, the sums of resultant arrays can be written as:

sum(array1')  = sum(array1) + { sum(array2[l...r]) - sum(array1[l...r]) }
sum(array2')  = sum(array2) - { sum(array2[l...r]) - sum(array1[l...r]) }

In terms of prefix sums, we can write it as follows:

sum(array1')  = sum(array1) + { pre2[r] - pre2[l-1] - pre1[r] + pre1[l-1] } = sum(array1) - pre1[r] + pre2[r] + pre1[l-1] - pre2[l-1] 
sum(array2')  = sum(array2) - { pre2[r] - pre2[l-1] - pre1[r] + pre1[l-1] } = sum(array2) + pre1[r] - pre2[r] - (pre1[l-1] - pre2[l-1])

So basically, for a fixed r :

• to make sum1 larger we maximize pre1[l-1] - pre2[l-1]
• to make sum2 larger we minimize pre1[l-1] - pre2[l-1]

We will try to account both the possibilities for each r and find the maximum sum that we can obtain.

Implementation

1. We will iterate through the arrays and try to maximize the sum of array1 and array2 (independently) by choosing the current position as r and choosing the optimal l.
2. We will maintain the prefix sum of both the arrays as we iterate through the arrays in variables pre1 and pre2.
3. We will also keep track of the maximum and minimum values of pre1 - pre2 and keep updating them as we move to the next position.
4. At each position we will try to maximise the sum of array1 by using the max value of pre1-pre2 so far and similarly maximise the sum of array2 by using the min value of pre1-pre2 so far.

PseudoCode

sum1 = sum(array1);
sum2 = sum(array2);
mn = 0, mx = 0, pre1 = 0, pre2 = 0, ans = max(sum1,sum2)

for i from 0 to n:

    //update the prefix sum values
    pre1 += array1[i], pre2 += array2[i]; 

    //try to maximise sum1 
    temp1 = sum1 - pre1 + pre2 + mx;
    ans = max(ans,temp1);

    //try to maximise sum2
    temp2 = sum2 + pre1 - pre2 - mn;
    ans = max(ans, temp2);

    //update the max and min values of pre1-pre2 obtained so far.
    mx = max(mx, pre1 - pre2);
    mn = min(mn, pre1 - pre2);

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Question 4

Analysis

This is a variation of the BFS problem, except that now we also need to keep a track of the number of obstacles we have removed to reach a cell. We can simply BFS over the cells to find the optimal solution.

Implementation

We will maintain a queue for the states (r,c,number of obstacles that we can still remove, steps taken to reach this cell) and perform a BFS over the states while updating the relevant parameters. The time complexity of the solution will be O(N*M*K) as each cell can be visited at most K times.

PseudoCode

shortestPath(grid, k):
        if len(grid) == 1 and len(grid[0]) == 1:
            return 0

        queue = queue([(0,0,k,0)])
        visited = set([(0,0,k)])

        if k > (len(grid)-1 + len(grid[0])-1):
            return len(grid)-1 + len(grid[0])-1

        while queue:
            row, col, eliminate, steps = queue.popleft()
            for new_row, new_col in [(row-1,col), (row,col+1), (row+1, col), (row, col-1)]:
                if (new_row >= 0 and
                    new_row < len(grid) and
                    new_col >= 0 and
                    new_col < len(grid[0])):
                    if grid[new_row][new_col] == 1 and eliminate > 0 and (new_row, new_col, eliminate-1) not in visited:
                        visited.add((new_row, new_col, eliminate-1))
                        queue.append((new_row, new_col, eliminate-1, steps+1))
                    if grid[new_row][new_col] == 0 and (new_row, new_col, eliminate) not in visited:
                        if new_row == len(grid)-1 and new_col == len(grid[0])-1:
                            return steps+1
                        visited.add((new_row, new_col, eliminate))
                        queue.append((new_row, new_col, eliminate, steps+1))

        return -1

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Question 5

Analysis

Claim: We can only reach (m,n) iff gcd(m,n) = 2^k for some k >= 0.

Proof: Lets prove it by mathematical induction.

• Firstly, we can reach (1,1) as we start from it and gcd(1,1) = 1 = 2^0.
• Now, let us assume that we can reach some (x,y) such that gcd(x,y) = 2^k for some k>=0. From (x,y) we can go to (2x,y), (x,2y), (x,y-x), (x-y,x).
• It can be seen that if we go to (x,y-x) or (x-y,x) the gcd remains the same by the virtue of the property gcd(a,b) = gcd(a,b-a). Hence the gcd is still 2^k for some k>=0.
• Now consider the transitions to (2x,y). We can write y = (2^k)*z for some z.
  • Case 1: z is divisible by 2. Now the gcd(2x,y) = 2^(k+1).
  • Case 2: z is not divisible by 2. The gcd(2x,y) remains the same that is 2^k
• The analysis for (x,2y) is similar.

Hence by the principal of mathematical induction we can prove that any cell (m,n) is only reachable iff gcd(m,n) = 2^k for some k>=0.

Implementation

We can use the built in gcd utility or write our own gcd function using the Euclidean algorithm. Each testcase can then be answered in O(log(max(n,m)).

PseudoCode

gcd(a,b):
      if(b==0) return a
      return gcd(b,a%b)

solve(n,m):
      g = gcd(n,m)
      return g&(g-1) == 0

8 months ago

Akshay Sharma 990

Chandigarh

Problem 3

Overview

1. We are given an array than has n element and a variable X
2. We are allowed to do only one operation which is select any index and increase its value by 1.
3. We can only do the given operation X times.
4. As an output we have to print the maximum frequency of any element.

PreRequist

Sliding window and Sorting

Approach

• First, we will sort the array in ascending order
  • As a starting step we will be initialling some element that is sum (To store the sum of sliding ),beg=0 and ans=0 (to store the frequency of array)
  • iterate over the array and Increment sum by arrend
  • Inside iteration, iterate another loop until the value of [( end – beg + 1) * arr[end] – sum] is less than X and perform the following operations:
  • Decrement the value of sum by arr[beg] and increment beg with 1 -After completing the above steps, all the elements over the range [beg, end] can be made equal by using at most X operations. Therefore, update the value of ans as the maximum of ans and (end – start + 1).
  • Finally print the answer and u are all set -Time Complexity: O(NlogN).

8 months ago

Akshay Sharma 990

Chandigarh

Question 2

Overview

• The question statement and sample example is also well elaborated still let breakdown further into one line
  • Given two strings and we need to find check if the difference between the frequency of each letter is less than equal to 3 or not if the frequency of difference of each letter in both words is less than 4 then we can print possible otherwise not possible.

PreRequist

• General knowledge of loops and frequency array and basic maths of primary school Xd.

Approach

• Create two frequency arrays name freq1 and freq2 that will store the frequency of each letter that appears in the word1 and word2
• Maintain a boolean flag variable and initialise it to true.
• After that, just iterate threw the freq array any of the above and check if the difference between the frequency of each letter is smaller than 4 or not, if the condition becomes false set the flag as false and break the loop -Print the and if flag is true print Possible else not possible
• Time Complexity : O(NlogN)

18 months ago

Zaheer Ismail Shaikh • 10

```py

def f(n,a1,a2):

#looking for which idx value is greater and replacing -1 with that value 
  new = [-1]*n
  for i in range(n):
    if a2[i] < a1[i]:
        new[i] = a1[i]
  best = 0 
  s2 = sum(a2)
  i = 0 

#finding longest subarray of new values e.g for tc 2 : new[-1, 40, -1, 70, 30]

# arr1=[20,40,20,70,30] arr2 =[50,20,50 ,40,20] means we can replace 70,30 with last two of arr2
  while i<n:
    cs = s2
    j = i
    while j<n and new[j]!=-1:
      cs-=a2[j]
      cs+=new[j]
      j+=1
    best = max(best,cs)
    i+=1
  return (max(best,sum(a1),sum(a2)))

t = int(input())
for _ in range(t):
  n = int(input())
  a1 = list(map(int,input().split()))
  a2 = list(map(int,input().split()))
  print(max(f(n,a1,a2),f(n,a2,a1)))

```
 

13 months ago

Ayush Agarwal • 20

Mumbai

Q1 : Maximum Score Of Spliced Array - LeetCode