4 ms·

"You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one?" Sum(Array) - 1000000(100000

"You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one?" Sum(Array) - 1000000(1000000 + 1)/2 = X For the other part it's just 1000000(1000000 + 1)/2 - Sum(Array) = Y EDIT: n*(n+1)/2 is the formula for the sum of the numbers from 1 to n

raptrex 16y ago
For finding the duplicate integer, I'm kind of lost. Say you have an array: 1,1,2,3,4. According the the equation: 11 - 5(6)/2 = -4?
- darkxanthos 16y ago
  11 - 4*(4+1)/2 = 11 - 10 = 1 n is not an index... it's the last number. I wasn't explicit, sorry. :)
- Stormbringer 16y ago
  it is based on the formula (n^2 + n)/2 picture it like finding the area of a trinagle that is half of a square (long side goes from diagonally opposite corners) formula for area of a square is n^2, so we need half that. What about +n part of it? It is because we are dealing in discrete chunks, not smoothly continuous. --- Alternately, imagine a series of children's blocks 1 2 3 now we have a 'triangle' with left side 3 high and bottom 3 wide. IF we make an identical triangle and rotate it round so that they fit together to make a rectangle, it looks like this 1 + 3 2 + 2 3 + 1 This makes a rectangle 3 x 4, and we should be able to figure out that this gives us an area of 12. So the original triangle ( 1,2,3 ) gives us half that and thus the sum from 1 to 3 is 6. So the pattern for summing the numbers 1 through N is to take a square of length N, add 1 to one of its sides, so it has sides of length N and N+1, and then find the area (which is always N^2 + N) and then halve that.
JeanPierre 16y ago
This function would be good if you know that all other integers are in the array once. However, this isn't elaborated within the question. A perfectly legal array with the restrictions we've been given is this: [1, 3, 3, 9, 42] All numbers in the array are integers between 1 and 1,000,000, and one integer is in the array twice. As for the solution, allocate 1,000,000 bits and do a "bucket sort". If the next number in the array is n, check if the nth bit is 1. If it is, you've found the integer appearing twice. If the nth bit is 0, change it to 1 and continue.
- darkxanthos 16y ago
  Good point tyvm for correcting me. Using just a bit in a bucket sort is a great approach.
- deleted 16y ago
  [deleted]

raptrex 16y ago

For finding the duplicate integer, I'm kind of lost. Say you have an array: 1,1,2,3,4. According the the equation: 11 - 5(6)/2 = -4?

darkxanthos 16y ago
11 - 4*(4+1)/2 = 11 - 10 = 1 n is not an index... it's the last number. I wasn't explicit, sorry. :)
Stormbringer 16y ago
it is based on the formula (n^2 + n)/2 picture it like finding the area of a trinagle that is half of a square (long side goes from diagonally opposite corners) formula for area of a square is n^2, so we need half that. What about +n part of it? It is because we are dealing in discrete chunks, not smoothly continuous. --- Alternately, imagine a series of children's blocks 1 2 3 now we have a 'triangle' with left side 3 high and bottom 3 wide. IF we make an identical triangle and rotate it round so that they fit together to make a rectangle, it looks like this 1 + 3 2 + 2 3 + 1 This makes a rectangle 3 x 4, and we should be able to figure out that this gives us an area of 12. So the original triangle ( 1,2,3 ) gives us half that and thus the sum from 1 to 3 is 6. So the pattern for summing the numbers 1 through N is to take a square of length N, add 1 to one of its sides, so it has sides of length N and N+1, and then find the area (which is always N^2 + N) and then halve that.

JeanPierre 16y ago

This function would be good if you know that all other integers are in the array once. However, this isn't elaborated within the question. A perfectly legal array with the restrictions we've been given is this: [1, 3, 3, 9, 42] All numbers in the array are integers between 1 and 1,000,000, and one integer is in the array twice. As for the solution, allocate 1,000,000 bits and do a "bucket sort". If the next number in the array is n, check if the nth bit is 1. If it is, you've found the integer appearing twice. If the nth bit is 0, change it to 1 and continue.

darkxanthos 16y ago
Good point tyvm for correcting me. Using just a bit in a bucket sort is a great approach.
deleted 16y ago
[deleted]