10 weeks ago

Rohit • 610

Hyderabad

Question 1

In a science research lab, combining two nuclear chemicals produces a maximum energy that is the product of the energy of the two chemicals. The energy values of the chemicals can be negative or positive. The scientist wishes to calculate the sum of the energies of the two chemicals which produces maximum energy on reaction.

Write an algorithm to find the sum of energy of the two chemicals which produces maximum energy on reaction.

Input

The first line of the input consists of an integer - numrChem, representing the number of chemicals (N).

The second line consists of N space-separated integers- ener0, ener1 ....... enerN-1 representing the energies of the chemicals.

Output

Print an integer representing the sum of energy of the two chemicals which produces maximum energy on reaction

Constraints

• 0 <= numOfChem <= 10^6
• -10^6 <= eneri <= 10^6
• 0 <= i <= numOfChem

Example

Input

9-3 8-6-7 8 10

Output:

19

Question 2

An employee in an organization has begun working on N projects (numbered 0 to N-1). Each week he/she can work on a single module of one of the projects. The modules that are chosen on any two successive weeks should come from different projects. A project i can have at most Ci modules.

The modules of the projects are such that a module is completed in a week.

Write an algorithm to determine the number of weeks the employee can work on projects following the above-mentioned rules.

Input

The first line of the input consists of an integer - num, representing the number of projects (N).

The next line consists of N space-separated integers - projC0, projC1, projCN-1, representing the number of modules of the projects.

Output

Print an integer representing the maximum number of weeks the employee can work on the projects

Constraints

• 1 <= num <= 5*10^4
• 1 <= projCi <= 10^7
• ΣprojCi <= 10^5
• 0 <= i < num

Example

Input:

3
7  2  3

Output:

11

8 months ago

Akshay Sharma 990

Chandigarh

Question 2

Approach/intuition

• If we analyse this test case given in the problem and try to understand the problem then the solution doesn't seem that hard.
• For the given test case 7,2,3 than an employee can work for a maximum of 11 weeks on the projects. If an employee starts his work with one that requires the highest number of weeks which is 7 week and also end with that week then we are able to get a maximum of 11 weeks.
• So the solution always exits as sum_of_all_element if The difference between Maximum_Element-Other_Element<=1 || Sum_of_other_element >Maximum_Element.
• If none of the conditions satisfies then the sum of other elements excluding maximum is less than the maximum_element then answer will going to be Sum_Of_other_Element*2+1
• We can easily calculate the sum using for loop
• Time Complexity: O(N)

Pseudo Code

for (int i = 0; i < n; i++)
{
    cin >> a[i];
    mx = max(a[i], mx);
    sum += a[i];
}
sum -= mx;
if (sum >= mx || sum - mx == 1)
{
    cout << sum + mx << "\n";
}
else
{
    cout << (sum * 2) + 1 << "\n";
}

8 months ago

Akshay Sharma 990

Chandigarh

Question 1

Approach

• The question wants to ask the sum of the two largest elements in the given array.
• We can easily calculate that by sorting the array and counting the number of negative elements in array
• If the number of negative elements in the array is greater than 1 then there is the possibility that the product of two negative elements give the largest value.
• So if the number of negative elements is greater than 1 we can check max(a[0]*a[1],a[n-1]*a[n-2])
• If maximum is from the starting we can print a[0]+a[1] else we can print a[n-1]+a[n-2]
• Time complexity:O(NLogN)

Pseudo Code

  Take input of the array
     cnt Number of negative elements 
  sort the array from 0 to n-1
     let start=a[0]*a[1] and end =a[n-1]*a[n-2]
     check maximum product 
     if(start>end)
         print a[0]+a[1]
     else 
        print arr[n-1]+arr[n-2]