So here are solutions. To make it easier to read, I'll repeat tasks here. All tasks start with the same statement:

You have an array with integers sequence from 1 to 1000:

```
[1, 2, 3, 4, 5, ..., 1000]
```

# 1. Easy

An item with value `x`

was removed, so the array became like:

```
[1, 2, 4, 5, ..., 1000]
```

Then the array was shuffled. How to find `x`

in `O(n)`

time and `O(1)`

memory?

## Solution

Just sum up all items and subtract the result from 500500 (a sum of integers from 1 to 1000 inclusively).

# 2. Harder

An item with value `x`

was replaced with `x - 1`

so the array became like:

```
[1, 2, 2, 4, 5, ..., 1000]
```

Then the array was shuffled. Again, you need to find `x`

in `O(n)`

time and `O(1)`

memory.

## Solution

Just summing up all elements won't give anything — it'll always be 500499. Is there a way to “amplify” values, so 3–1 will impact the result differently than 495–1? Yes, there is one, and it's just squaring items.

Indeed, $x$ was replaced with $x - 1$ , which means the result — sum of squares — gets less than expected value by

To find $d$ , subtract actual squares sum from expected value — sum of squares of 1 to 1000 which is 333,833,500. Then,

Yes, it's that simple!

# 3. Hard

An item with value `x`

was replaced with `y`

where `y`

is any integer from `1`

to `1000`

, so the array became like

```
[1, 2, 9, 4, 5, ..., 1000]
```

The array was shuffled, and your task again is to find `x`

and `y`

in `O(n)`

time and `O(1)`

memory.

## Solution

Summing up values or squares won't give anything but what if we do both? We can substitute $y$ with $x - k$ where $k$ is any integer, possibly negative. To find $k$ we sum all items and subtract the result from 500500 which immediately gives $k$ . Then we may use a formula similar to one from 2nd problem:

where $d$ is the difference of expected and actual squares sum.

And finally,

## Top comments (0)