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

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

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 algorithm in the problem. Make sure ALL test cases return expected outputs by providing output screenshots.

Hint: Use merge sort/quicksort

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;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String[] parts = br.readLine().trim().split(" ");
        int n = Integer.parseInt(parts[0]);
        int k = Integer.parseInt(parts[1]);
        int[] ages = new int[n];

        for(int i = 0; i < n; i++) {
            ages[i] = Integer.parseInt(br.readLine().trim());
        }

        for(int i = 0; i < k; i++){
            parts = br.readLine().trim().split(" ");
            int s1, e1, s2, e2;
            s1 = Integer.parseInt(parts[0]);
            e1 = Integer.parseInt(parts[1]);
            s2 = Integer.parseInt(parts[2]);
            e2 = Integer.parseInt(parts[3]);

            sb.append(String.format("%d\n",solve(n,ages,s1,e1,s2,e2)));
        }
        System.out.print(sb);
    }

    /*
    Solves a test case

    Parameters:
    n    : int        - number of ages given
    ages : array-like - list of ages
    s1   : int        - start index of Danny's family. Also Danny's index
    e1   : int        - end index of Danny's family
    s2   : int        - start index of Danny's found family
    e2   : int        - end index of Danny's found family

    Return the age of Danny's soulmate
    */
    public static int solve(int n, int[] ages, int s1, int e1, int s2, int e2) {
      // TODO  
    }
}

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₂ ≤ 10¹4
1 ≤ S₁ ≤E <N
1 ≤ S₂ ≤ E2 ≤ N
Transcribed Image Text: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₂ ≤ 10¹4 1 ≤ S₁ ≤E <N 1 ≤ S₂ ≤ E2 ≤ N
Expert Solution
steps

Step by step

Solved in 4 steps with 2 images

Blurred answer
Knowledge Booster
Inference
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education