Quickest way to find the replaced number

Question

Let's say we have an Integer array with values from 1 to 1000000. Suppose a single number is replaced with '-1'. What is the quickest way to find the number that is replaced? Is there a better way apart from the normal looping/searching linearly?

Please note the size of the array can be anything, the above is just an example to consider data of large size. Consider the array size as "N" containing the values from 1 to N.

Are there any additional constraints, such as the array (except for the -1) being sorted in ascending/descending order? Otherwise it is impossible to get better than a linear search: You *have* to look at every position in the array to tell where the -1 is. — Luatic, Jul 13 '23 at 11:02
Unclear. Do you mean that the array contains exactly 1000000 elements, with one each of every value from 1 to 1000000? — user207421, Jul 13 '23 at 11:25
By the way, if there is a web page that states the original problem, it would be a good idea to edit the question to include a link to that page. Questions like this might be on programming practice / challenge sites, such as LeetCode, CodeSignal, HackerRank, ... — Old Dog Programmer, Jul 13 '23 at 22:52
@OldDogProgrammer No, it would be good practice to *quote the web page here.* — user207421, Jul 14 '23 at 00:21
@user207421 I didn't intend to mean "either or". I think *both* is a good idea. — Old Dog Programmer, Jul 14 '23 at 01:07

score 1 · Answer 1 · answered Jul 13 '23 at 15:13

Try it like this.

populate the numbers in a list.
shuffle them (to make the choice random).
replace any index with -1 (returning the original value)
Now compute the sum of numbers from 1 to 1,000,000 inclusive.
then iterate thru the list, subtracting each number in the list from that sum.
then correct the subtraction of -1 by adding 1 to the sum
sum now contains the replaced number

int n = 1_000_000;
List<Integer> list = IntStream.rangeClosed(1, n).boxed()
        .collect(Collectors.toCollection(ArrayList::new));

Collections.shuffle(list);

int index = 132939; // select a value between 1 and 1,000,000 inclusive

int originalValue = list.set(index, -1);
long sum = ((long)n*(n+1))/2L;

for (int i = 0; i < list.size();i++) {
      sum -= list.get(i);
}

System.out.println(sum - 1);
System.out.println(originalValue);

prints

351316
351316

score 0 · Answer 2 · answered Jul 13 '23 at 11:06

0

I assume that array is not sorted.

You can calculate the sum of an arithmetic sequence and in one loop subtract every element from this sum.

Answer is value of sum variable-1 (because we subtract -1 from array somewhere)

answered Jul 13 '23 at 11:06

ECHU

156
9

Agree this is one of the best possible ways. Just curious is there any other way to identify such differences when the data set is large? – Eternal_Explorer Jul 13 '23 at 11:14
1

You can divide dataset in small packages and calculate for them sum of their elements asynchronously and on every thread end subtract partial sum from base sum of an arithmetic sequence -> this is the same answer, but I want to pointed out You can easily use it asynchronously. I do not know any better (and dont think there is any better which is also that simply) - maybe if only time is important some dynamic trick with memory usage can do thing faster – ECHU Jul 13 '23 at 11:23
1

How is this better than a linear search? It just seems more complex to me. – Luatic Jul 13 '23 at 12:04
3

@Luatic Linear search only gives you the position of the -1, not the value it replaced. I misunderstood the question too. If the array is randomly shuffled values from 1 to n and 1 <= x <=n is replaced by -1, then x = (n(n+1)/2) - arraysum - 1. – Simon Goater Jul 13 '23 at 13:18
@SimonGoater ah, thanks for clarifying that. In that case, this is indeed the way to go. – Luatic Jul 14 '23 at 09:37

Quickest way to find the replaced number

2 Answers2