Find the Disappeared Numbers
Problem
The array has n numbers, and every number is between 1 and n. Some numbers appear twice and some do not appear. Print the numbers from 1 to n that do not appear, in ascending order, separated by spaces. Print none if every number appears.
Constraints
- 1 <= n <= 10^5
- 1 <= a[i] <= n
Examples
Input
8 4 3 2 7 8 2 3 1
Output
5 6
Solutions
The sign of a number works as a flag. For each value v we make the number at index v - 1 negative. Positions that stay positive show the missing values. No extra array is needed.
/*
* Problem : Disappeared numbers.
* Input : n, then n integers.
* Output : Missing numbers.
* Approach: Negative marks.
* Time : O(n)
* Space : O(1)
* 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) {
// Step 1: Use the array itself as a table. For a value v, make the number at index v - 1 negative.
int[] data = a.clone();
for (int i = 0; i < data.length; i++) {
int index = Math.abs(data[i]) - 1;
if (data[index] > 0) {
data[index] = -data[index];
}
}
// Step 2: An index whose number is still positive was never marked, so index + 1 is missing.
StringBuilder result = new StringBuilder();
for (int i = 0; i < data.length; i++) {
if (data[i] > 0) {
if (result.length() > 0) {
result.append(' ');
}
result.append(i + 1);
}
}
return result.length() == 0 ? "none" : result.toString();
}
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();
}
System.out.println(solve(a));
}
}
Hints (2)
- Why use abs() when we read a value?
- What does a positive number at index i tell us?