Contents

Problem Description:

I am a novice in solving DSA problems. I am stuck to start an approach to this problem. Can someone please provide me help or reference to this problem?

Question

N people are standing in a queue based on descending order of their age, find the last person’s name with the given age K. If not found, return "Not found".

Input Format

• First line contains two integers N, K – Number of people, the given age.

• Second line contains N integers – The ages of people.

• Third line contains N strings – The names of people.

Output Format

• Print the name of the last person with the given age or "Not found" if not present.

Sample Input

``````6 30
80 30 30 7 3 3
Sam Will Roy Lane Pam Jim
``````

Sample Output

``````Roy
``````

Explanation

• The people with age 30 in order are Will, Roy. The last person from them is "Roy".

Constraints

``````1 <= N <= 10^5
1 <= K, Age[i] <= 10^5
1 <= |Person's name| <= 10
``````

Here is my code:

``````import java.util.*;

class FindLastPersonOfAgeK{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
List<Integer> ages = new ArrayList<Integer>();
List<String> people = new ArrayList<String>();
for (int i = 0; i < n; i++) {
}
for (int i = 0; i < n; i++) {
}
String ans = findLastPersonOfAgeK(ages, people, k);
System.out.println(ans);
sc.close();
}

static String findLastPersonOfAgeK(List<Integer> ages, List<String> people, int k){

}
}
``````

## Solution – 1

1. Array/list is a suitable data structure for this problem.
2. To improve the complexity of searching, you can use binary search to find the index of the last element with `age = K`.
3. Using the found index, you can find the name of the person.

## Solution – 2

You don’t need to use `List` since you know the number of elements – it is the first number on the first line of input entered by the user. In the code in your question, it is the variable `n`. Hence you can use arrays rather than `List`s.

Assuming the input is always valid, i.e. all the integers are not negative and the ages are entered in descending order, all you need do is iterate the `ages` array in reverse order. Once you find an element of `ages` that equals `k`, you have found the last element. Get its index and return the element in `people` at that index.

As an optimization, once an element in `ages` is greater than `k`, there is no need to continue iterating through `ages`.

``````import java.util.Scanner;

public class FindLastPersonOfAgeK {

public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] ages = new int[n];
String[] people = new String[n];
for (int i = 0; i < n; i++) {
ages[i] = sc.nextInt();
}
sc.nextLine();
for (int i = 0; i < n; i++) {
people[i] = sc.next();
}
String ans = findLastPersonOfAgeK(ages, people, k);
System.out.println(ans);
sc.close();
}

static String findLastPersonOfAgeK(int[] ages, String[] people, int k) {
for (int i = ages.length; --i >= 0;) {
if (ages[i] == k) {
return people[i];
}
else if (ages[i] > k) {
break;
}
}
}
}
``````

Note that after calling method `nextInt` (of class `java.util.Scanner`) and before calling method `next` (also of class `java.util.Scanner`) you need to call method `nextLine`. Refer to Scanner is skipping nextLine() after using next() or nextFoo()

When I run the above code, using the sample input from your question, I get the following:

``````6 30
80 30 30 7 3 3
Sam Will Roy Lane Pam Jim
Roy
``````

The first three lines above are the inputs and the last line is the value returned by method `findLastPersonOfAgeK`.

Rate this post
We use cookies in order to give you the best possible experience on our website. By continuing to use this site, you agree to our use of cookies.