2

An array contains N elements, each element within the range 1 <= K <= X where X <= N. The elements are in no particular order, but there are many duplicate elements. I am wondering if there is a way to iterate over the array, stopping as soon as one of every integer 1-X has been seen, and doing so without allocating an additional array and without sorting the original array.

Edit: The array is guaranteed to contain all values 1-X. X is a parameter, not a constant.

Edit:

More generally, I am wondering if there is some known way of combining unique consecutive integers into a sum or a product, such that the value of that sum or product can tell whether or not one of those integers is a part of it. Something like multiplying unique primes together.

Thanks

John Savage
  • 103
  • 6
  • **I am wondering if there is a way to iterate over the array**, That's a good idea and keep going to do that. Now, what did you tried so far ? – Michi Sep 30 '15 at 18:38
  • 1
    Use bits of an integer if N < 32? – C.B. Sep 30 '15 at 18:39
  • Initially I was thinking to map all of the integers 1-X to a unique prime number, and compose a main number by multiplying all primes 1-X. Then divide the main number by the mapped prime. If that prime is a factor, it has not been seen yet. If it is not a factor, it has already been divided out. But this array may be very, very large, so integer overflow would be an immediate issue and I don't know of a way to map the integers to primes. – John Savage Sep 30 '15 at 18:42
  • That would quickly exceed even a 64-bit integer. You'd have to use a big number library with arbitrary sized numbers. At that point you effectively have an array, just with a rather inefficient representation. – John Kugelman Sep 30 '15 at 18:45
  • @C.B. this is a good idea, but the input array size will be far larger than 32 or 64. – John Savage Sep 30 '15 at 18:45
  • It is hard to keep track of data without a data structure. – John Coleman Sep 30 '15 at 18:45
  • 2
    Your explanation of your goal does not match the title of this question. Your explanation has nothing to do with finding the unique elements, but rather in determining whether the array contains at least one entry for each of the values 1 through X – FredK Sep 30 '15 at 18:46
  • 1
    Can you mutate the original array? If so, answer is here http://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space – C.B. Sep 30 '15 at 18:49
  • That is not true FedK. The array is known to contain all values 1 - X. I simplified the problem I am looking to solve by leaving out irrelevant details. The function will have all of the information it needs as soon as all of the unique elements have been seen. – John Savage Sep 30 '15 at 18:49
  • Is X a fixed constant or a parameter of the problem instance? In other words, is X specified by the problem, or by the problem instance? – Patrick87 Sep 30 '15 at 18:51
  • Iterate over the array `X` times, looking for the first occurrence of `X`. Compare its index with the maximum index found so far, and finally that will be the answer. – Weather Vane Sep 30 '15 at 18:54
  • You could loop `for i = 1 to X` and inside that loop go `for j = 1 to N` and stop when you see `i` at position `j` of the array. Record this as the minimum depth you have to walk into the array to find all elements. Only replace this value for subsequent `i` values if it's bigger than the existing value. After looping all `X` values, the minimum depth will be the depth you have to walk to in order to see all elements. It's O(1) storage and O(XN) time. – Patrick87 Sep 30 '15 at 18:55
  • Can you swap some elements in the array, or would that break the no sorting rule? – m69's been on strike for years Sep 30 '15 at 20:41
  • @m69 Yes, you are allowed to modify the array, but in this situation the index is an important piece of information to the element. – John Savage Sep 30 '15 at 20:44

3 Answers3

2

There is a trivial way, but it is exceptionally inefficient. Just use two nested loops. Untested pseudocode:

   lastIndex = 0;
   containsAll = true;
   for ( i=1; i <= x; i ++ ) {
       for ( j=0; j < n; j++ ) {
          if ( array(j) == i ) {
            if ( j > lastIndex ) {
               lastIndex = j;
            }
            break;
          }
       }
    }
FredK
  • 4,094
  • 1
  • 9
  • 11
  • OP wrote *"Edit: The array is guaranteed to contain all values 1-X"*. He wants to find the array index where all `1...X` are contained. – Weather Vane Sep 30 '15 at 18:57
  • Same as what I thought. Note that if he wants the depth into the array he has to search to see all of the elements, you can keep track of that pretty easily in your code. – Patrick87 Sep 30 '15 at 18:58
  • OK, I have modified the answer to find the index lowest index. – FredK Sep 30 '15 at 19:06
0

Well you know what X is - so sum(1..x) = (x * (x +1))/2

foreach element in array
Look back and see if value exists, if no add to sum
If sum == sum(1..x) - then break

edit:

Seems that my pseudo code left too much to be filled.. here is c# version - idx ends beeing 12 - the position of first 6. Array unordered with duplicates.

  var numbers1 = new int[] { 8, 7, 2, 9, 4, 1, 1, 3, 1, 5, 5, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
  var x = 9;
  var sumxResult = (x * (x + 1)) / 2;
  var idx = 0;
  var sumx = 0;

  for (var i = 0; i < numbers1.Length - 1; i++)
  {
    var n = numbers1[i];
    idx = i;
    var found = false;
    //seek back:
    for (var j = i-1; j >= 0; j--)
    {
      var n1 = numbers1[j];
      if (n1 == n)
      { found = true; break; }
    }

    if (!found)
    {
      sumx += n;
      if (sumx == sumxResult)
        break;
    }
  }
  Console.WriteLine(idx);
Rune Andersen
  • 1,650
  • 12
  • 15
  • This would work on a sorted array, but this array is not necessarily sorted. The element's index is also a necessary piece of information in this case, so I don't believe sorting is an option. – John Savage Sep 30 '15 at 20:42
  • the idea is that you don't need sorting - the order for adding numbers together does not matter. You use (x*(x-1))/2 to verify that you have visited all 1-x once in some order. This will perform the worst if it is ordred with only one of each 1-x - FredK's solution will be best then. If unordered with multiple values foreach 1-x this will be better. – Rune Andersen Sep 30 '15 at 21:44
  • I think you're looking for (x*(x+1)/2), but even still, this will not work in a situation where there are duplicates in the array. – John Savage Sep 30 '15 at 23:03
  • Your right - typing mistake. I have added a working version - since you could not see what I meant :) – Rune Andersen Oct 01 '15 at 19:33
0

The difficulty is not in finding the numbers, but in remembering which numbers you've already encountered. This is necessary to know when you've found every number, and also to avoid counting the same number multiple times.
I see two approaches to make sure you've found every number at least once, without using additional storage:

  1. Search for each number in turn: search 1, then 2, then 3, ... then X. (as in FredK's answer)
  2. Keep track of found numbers by moving them into place: move item with value n to position n.

This second option would consist of iterating over the array, and for every value you encounter, swapping it with the item whose index is the found value. If the item at that index already has the correct value, you've encountered the number before.
To avoid counting numbers twice, you should only count the values that are found in place, or are moved backwards into place. Values that are moved forward into place will be counted when you iterate over that place later.

m69's been on strike for years
  • 11,835
  • 3
  • 34
  • 57