Danny has been single all his life. He is desperate to find a match. While reading a shady tabloid column, he saw a surefire way to find a soulmate. Step 1: Find a family with at least as many children as yours. For example, if Danny's family has K children, himself included, he has to find a family with at least K children. Step 2: Find your birth order in your family. For example, if Danny is 20 years old and his siblings are 12, 15, 18, 32, and 33 years old, Danny's birth order is 3 since he is the 3rd oldest. Step 3: Find the person in the other family with the same birth order. For example, if the other family has children with ages 20, 21, 25, 27, 37, and 40, Danny's soulmate is the one aged 27. Danny can't wait to find his soulmate. He is already done with step 1. Can you help him with steps 2 and 3? Input Format Input contains several queries to be processed. Input begins with a line containing two space-separated integers: N and K. N is the number of ages given. K is the number of queries to answer. N lines follow. Each line contains one integer A,, indicating the age of the ith person in hours. The first person is labeled as Person 1. The last person is Person N. K lines follow, each representing one query. Each line contains four space-separated integers S₁, E1, S2, E2 indicating the start index of the first family, end index of the first family, start index of the second family, and end index of the second family. For example, if the query contains "1 5 10 20", the first family is Person 1 until Person 5 in the prior list. The second family is Person 10 until Person 20. Also, assume Danny is Person S₁. Constraints 1≤ N≤ 105 1≤ K≤ 5.10³ 0 ≤ Aį ≤ 107 All A; are guaranteed to be distinct. 1 ≤ E₁-S₁ ≤ E2 - S₂ ≤ 104 1 ≤ S₁ ≤ E₁ ≤ N 1 ≤ S₂ ≤ E2 ≤ N
Information is present in the screenshot and below. Based on that need help in solving the code for this problem in java. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply divide-and-conquer
Output Format
Output consists of K lines.
For each query, output the age of Danny's soulmate in hours, similar to the input.
Sample Input 0
5 3
16
8
14
10
4
2 4 1 5
1 3 1 5
1 5 1 5
Sample Output 0
10
16
16
Sample Input 1
7 3
9
30
10
19
26
3
12
2 2 2 7
1 3 3 7
7 7 2 5
Sample Output 1
30
12
30
Sample Input 2
9 4
26
35
24
32
31
36
27
22
23
2 9 2 9
2 6 1 5
2 8 1 8
1 8 2 9
Sample Output 2
35
32
35
24
The actual code
import java.io.BufferedReader; public class Solution { for(int i = 0; i < n; i++) { for(int i = 0; i < k; i++){ sb.append(String.format("%d\n",solve(n,ages,s1,e1,s2,e2))); /* Parameters: Return the age of Danny's soulmate |
Step by step
Solved in 4 steps with 2 images