1

We're given N (3 <= N <= 50000) cards with unique numbers from 1 to N. We lost some 3 cards and our goal is to find them.

Input: first line contains number of cards N. Second line contains 3 numbers: sum of all left cards we have, sum of their squares and sum of their cubes.

Output: numbers of 3 lost cards in any order.

Here what I tried: I found the same 3 sums for lost cards and then check of possible numbers until three of them satisfy our sums.

Is there a faster solution? I have to pass 2sec time limit in Python with max N = 50000.

N = int(input())
lst = list(range(1, N+1))
s_rest, s2_rest, s3_rest = list(map(int, input().split()))

s = sum(lst)
s2 = sum([x**2 for x in lst])
s3 = sum([x**3 for x in lst])
# sums of 3 lost numbers
s_lost = s - s_rest
s2_lost = s2 - s2_rest
s3_lost = s3 - s3_rest


def find_numbers():
    """Find first appropriate option"""
    for num1 in range(s_lost):
        for num2 in range(s_lost):
            for num3 in range(s_lost):
                if (num1 + num2 + num3 == s_lost) and (num1**2 + num2**2 + num3**2 == s2_lost)\
                        and (num1**3 + num2**3 + num3**3 == s3_lost):
                    return (num1, num2, num3)

answer = find_numbers()
print(answer[0], answer[1], answer[2])

Examples

Input:

4

1 1 1

Output:

2 3 4

Input:

5

6 26 126

Output:

2 3 4

Legonaftik
  • 1,350
  • 3
  • 17
  • 33
  • 1
    Possible duplicate of [Easy interview question got harder: given numbers 1..100, find the missing number(s)](http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe) – Paul Hankin Jun 02 '16 at 08:42
  • Given your N is small (50000 at most), what's wrong with `set(range(1, N+1)).difference(input_numbers)` ? This is a much easier problem than the one I suggested is a dupe given this constraint on N, and a simple set-based problem which uses O(N) storage (rather than O(1) storage) works just fine. – Paul Hankin Jun 02 '16 at 08:47

5 Answers5

2

If your unknown numbers are x,y,z, then you have a system of three equations

x + y + z = a  //your s_lost
x^2 + y^2 + z^2 = b  //your s2_lost
x^3 + y^3 + z^3 = c  //your s3_lost

While direct solution of this system seems too complex, we can fix one unknown and solve simpler system. For example, check all possible values for z and solve system for x and y

 for z in range(s_lost):
 ....

Now let's look to new system:

 x + y  = a - z = aa
 x^2 + y^2 = b - z^2 = bb
 substitute
 x = aa - y
 (aa - y)^2 + y^2 = bb
 2 * y^2 - 2 * y * aa - bb + aa^2 = 0
 solve this quadratic equation for y
 D = 4 * aa^2 - 8 * (aa^2 - bb) = 8 * bb -4 * aa^2
 y(1,2) = (2*aa +- Sqrt(D)) / 4

So for every z value find:
- whether solution gives integer values of y
- then get x
- and then check if cube sum equation is true.

Using this approach you'll get solution with linear complexity O(N) against your cubic complexity O(N^3).

P.S. If rather simple mathematical solution for equation system does exist, it has complexity O(1))

MBo
  • 77,366
  • 5
  • 53
  • 86
1

This can be simplified by mathematical approach. You are given 3 equations and have 3 unknowns. 

sum(1+2+..+N) - x1 - x2 - x3 = a  
sum(1^2+2^2+..+N^2) - x1^2 - x2^2 - x3^3 = b  
sum(1^3+2^3+..+N^3) - x1^3 - x2^3 - x3^3 = c

Obviously sum(1..N) is 1/2 *N(N+1), while sum(1^2+2^2+3^2+..+N^2) is 1/6 *N*(N+1)*(2N+1) and sum(1^3+2^3+..+N^3) can be written as 1/4 *N^2 *(N+1)^2. Here are wolframalpha outputs: ∑k, ∑k^2, ∑k^3

At this point only thing left is solving given system of equations (3 with 3 unknowns is totally solvable) and implementing this. You only need to find one solution which makes it even easier. Running time is O(1).

Tomasz Plaskota
  • 1,329
  • 12
  • 23
0

Surely there exists a faster approach!

For N=50,000 your brute-force function would have to make up to 

N * N * N = 125,000,000,000,000

iterations, so this is not an option.

Additionally, you should check for num1 == num2 etc. to avoid duplicated numbers (the problem does not state it explicitly, but I understand 'We lost some 3 cards' means you need to find three different numbers satisfying the conditions given).

CiaPan
  • 9,381
  • 2
  • 21
  • 35
0

You can sort the list, and find the pairs such that a[i+1] =/= a[i]+1. For every such pair numbers [a[i]+1;a[i+1]) are missing. This would give you O(n log n) running time.

kilotaras
  • 1,419
  • 9
  • 24
0

I can give you an idea,

let sum1 = 1+2+3...n

let sum2 = 1^2+2^2+3^2...n

and p, q, r is three numbers given by input consecutively.

We need to search a, b, c. Iterate for c = 1 to N.

For each iteration,

let x = sum1 - (p+c)

let y = sum2 - (q+c*c)

so a+b = x and a^2+b^2 = y.

Since a^2+b^2 = (a+b)^2 - 2ab, you can find 2ab from equation a^2+b^2 = y.

a+b is known and ab is known, by a little math calculation, you can find if there exist a solution for a and b (it forms quadratic equation). If exist, print the solution and break the iteration.

It's an O(N) solution.

Teguh Suryo Santoso
  • 161
  • 6