Flipkart OA 2023 - Employee Performance Split

In an organisation, there are N employees, with IDs ranging from 1 to N. Based on the performance in the last financial year, the organisation's application assigns a performance score to each employee. The company’s overall performance score for the last financial year is represented by K. After giving all the employees their performance values, the application splits all the employees into two parts in such a way that:

• The sum of the largest performance value in the first group and the smallest performance value in the second group is always greater than or equal to K.
• The two groups may be of the same length or different lengths, but both groups must contain at least one employee.

Write an algorithm to find the number of ways the employees can be split while satisfying the above conditions.

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.

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.

Constraints:

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