Flipkart OA-5 2023

Problem Description

In an organization with N employees, each employee has a unique ID ranging from 1 to N. Based on performance in the last financial year, each employee is given a performance score. The company's overall performance target for the year is represented by K.

The task is to split all employees into two groups so that:

1. The sum of the highest performance score in the first group and the lowest performance score in the second group is at least K.
2. Both groups contain at least one employee, though the groups may have different numbers of employees.

Write an algorithm to determine the number of possible ways to split the employees into two groups while meeting the above condition.

Input Format:

• The first line contains an integer employee_size, representing the total number of employees (N).
• The second line contains N space-separated integers: employee_1, employee_2, ..., employee_N, representing the performance scores of the employees.
• The third line contains an integer companyPerformanceValue representing the company’s overall performance score (K).

Output Format:

• Print a single integer representing the number of ways the employees can be split. If no valid split is possible, print -1.

Constraints:

• 1 <= employee_size <= 10^6
• 0 <= employee_1, employee_2, ..., employee_N <= 10^6
• 0 <= companyPerformanceValue <= 10^6

Example:

Input:

4
3 1 7 4
6

Output:

2

Explanation:

The following splits are considered:

1. Split: ( (3) & (1, 7, 4) -> 3 + 1 = 4 )
   Since 4 is less than 6, this split will be rejected. (Count: 0)
2. Split: ( (3, 1) & (7, 4) -> 3 + 4 = 7 )
   Since 7 is greater than 6, this split will be accepted. (Count: 1)
3. Split: ( (3, 1, 7) & (4) -> 7 + 4 = 11 )
   Since 11 is greater than 6, this split will be accepted. (Count: 2)

Thus, the final output is 2.