ZSGoldberg
BAN USER@Roxanne - yep! Tried to capture that by saying the "the set of" indices and "the set of values" are the same. 'Sets' being lists not in any particular order
- ZSGoldberg January 29, 2014This is really interesting! To the question above, you'll be xoring every number in the array as well as every index in the array.
Eg if the missing element is 4, you'll be evaluating the expression that includes 2 copies of each number except 4,of which there will be only one.
That is, (a xor a) xor (b xor b) xor (c xor c)... xor MISSING_NUMBER. This is equivalent to 0 xor 0 xor 0...xor MISSING_NUMBER, Which is equivalent to the missing number itself.
Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same.
My understanding of the problem is that there is an unsorted array containing 98 ints between 1 and 100, thus missing one value in that range.
The sum of numbers 1 through 100 is equal to (101*100)/2 = 5050
If we take the sum of the numbers in our array and subtract it from 5050 the result should be the one missing int.
Easy enough to code but I'm on mobile
Fewer times through the loop, I considered the two to be equivalent. Looking at it now I think going through the extra loops is worthwhile for cleaner looking code
- ZSGoldberg January 25, 2014#include "stdio.h"
void printMinMaxInRange(int start, int end, int array[])
{
int i = 0;
int min = end;
int max = start;
while (i <= ((end - start) / 2))
{
if (array[i+start] > array[max])
max = i + start;
if (array[end - i] > array[max])
max = end - i;
if (array[i+start] < array[min])
min = i + start;
if (array[end - i] < array[min])
min = end - i;
i++;
}
printf("max %d at index %d\nmin %d at index %d\n",
array[max],max,array[min],min);
}
int main(int argc, char *argv[])
{
srand(time(NULL));
int a[101];
int i = 1;
while (i < 101)
{
a[i] = rand() % 1000;
i++;
}
printMinMaxInRange(25,75,a);
}
When you say everything is preferably O(1), are you just saying that faster is better? Clearly "contains" can't be O(1) unless its probabilistic (or unless the data structure is defined to contain at -most O(1) elements...)
- ZSGoldberg August 09, 2014