Number skipping algorithm?

Question

Python

There are n users registered in the Kinoshechka service. All but two users have visited the site in the past two months. You need to determine the id of users who have not visited the site.
Input format
The first line contains the number n — the number of registered users. This is an integer in the range 2 to
10 to the power of 6.
The second line contains space-separated distinct n - 2 integers. Each of them does not exceed n and is greater than zero.

Output Format
It is necessary to print two missing numbers in ascending order, separated by a space, in one line.
I solved it like this
The input.txt file contains

19
16 11 5 7 15 18 6 13 9 10 14 12 2 19 4 17 3

main.py file

with open('input.txt', 'r') as f:
    nums = f.read().splitlines()
    all_count=nums[0]
    rows=nums[1:]
    result_string=''
    for r in rows:
        arr=list(map(int, r.split()))
    arr.sort()
    for i in range(1, int(all_count)+1):
        if i not in arr:
            result_string+= str(i) +' ' 
    print(result_string)

It works correctly, but on the 7th test it does not pass because the execution time is more than 7 seconds, and there is a lot of data in input.txt.
How can the algorithm be optimized?

Answer 1

n = 19
numbers_as_string = '16 11 5 7 15 18 6 13 9 10 14 12 2 19 4 17 3'
numbers = [int(i) for i in numbers_as_string.split(' ')]

all_numbers = set(range(1, n + 1))
numbers = set(numbers)
sorted_diff = [str(i) for i in sorted(all_numbers.difference(numbers))]
print(' '.join(sorted_diff))

Answer 2

n = 19
visitors = '16 11 5 7 15 18 6 13 9 10 14 12 2 19 4 17 3'.split(' ')
missed = list(filter(lambda x: str(x) not in visitors, range(1, n+1)))

https://ideone.com/PxuDHE

Answer 3

This is a generalization of a well-known problem where one number is missing. There you can, for example, subtract all numbers from n(n+1)/2. Or xor all the numbers from 1 to n and all the numbers in the array.
For two numbers, you need to make some 2 equations, For example, find the sum of two numbers and the sum of their squares: The sum of the missing numbers is n * (n + 1) / 2 - (the sum of all numbers in the array). Here you need to be careful not to forget about a possible overflow (if your language is, for example, C ++). Sum of squares: The sum of the squares of all numbers from 1 to n minus the squares of all numbers in the array.
So you've found X+Y=A and X^2 + Y^2=B in O(n) two non-nested loops (one for the sum of squares 1..n, the other for processing all the numbers in the array).
Now solve the equations for X and Y: Express X in terms of Y from the first equation and substitute into the second. Solve the quadratic equation and get:
X = (A-sqrt(2B-A^2))/2, Y = (A+sqrt(2B-A^2))/2.
Here, although there are square roots, they eventually give whole numbers.

Answer 4

The idea is as follows:
1) Read the array
2) Sort
3) Use binary search

Answer 5

To search for missing numbers, it is not at all necessary to do the last loop, and even in a loop.
It is enough to linearly go through the sorted array once from the beginning to the end, checking at each step whether the condition arr[i]==arr[i]+1 is met, and if not, then arr[i] = this is your number.
It is possible in another way. If you know numpy, then first create a zero array with n positions, then write each number x so that arr[x]=x. And then, in one pass of the array, look for those positions that remain zero.
You can also come up with algorithms that will work exactly faster than a brutal loop within a loop.

Answer 6

Faced with. this task on Yandex.Practice.
I procrastinated on the solution for a long time, at first I also fell on the 7th test. As a result, I came to this decision, all tests pass (this is Java):

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int usersAmount = scan.nextInt();
        byte[] ids = new byte[usersAmount];
        int num;
        while (usersAmount > 2) {
            num = scan.nextInt();
            ids[num - 1] = 1;
            usersAmount -= 1;
        }
        int count = 0;
        for (int i = 0; i < ids.length; i++) {
            if (count<2) {
                if (ids[i] == 0) {
                    count++;
                    System.out.print((i+1) + " ");
                }
            } else {
                break;
            }
        }
    }
}