Take While and Drop While
Problem
Read numbers from the left while they are smaller than k. Print two lines: first the numbers that were read (the longest prefix of numbers smaller than k), then all the other numbers. Print the word empty for a line with no numbers.
Constraints
- 1 <= n <= 10^5
Examples
Input
5 1 2 5 1 7 4
Output
1 2 5 1 7
Solutions
Both parts depend on one thing: the first position that fails the test. We find it once (findFirst stops early) and cut the array there. Python has takewhile and dropwhile for exactly this.
/*
* Problem : Split a prefix.
* Input : n, the array, then k.
* Output : Two lines.
* Approach: Stop at the first match.
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(int[] a, int k) {
// Step 1: Find the first position that is NOT smaller than k. A stream stops at the first match (findFirst).
int split = java.util.stream.IntStream.range(0, a.length).filter(i -> a[i] >= k).findFirst().orElse(a.length);
// Step 2: Everything before the split is the "take while" part. Everything from the split is the "drop while" rest.
String taken = java.util.Arrays.stream(a, 0, split).mapToObj(String::valueOf).collect(java.util.stream.Collectors.joining(" "));
String rest = java.util.Arrays.stream(a, split, a.length).mapToObj(String::valueOf).collect(java.util.stream.Collectors.joining(" "));
return new String[] {taken.isEmpty() ? "empty" : taken, rest.isEmpty() ? "empty" : rest};
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
int k = scanner.nextInt();
System.out.println(String.join("\n", solve(a, k)));
}
}
Hints (2)
- Does the search continue after the first failure?
- What if every number is smaller than k?