Riddles, Brain Teasers, and more...

[Tony]

Yeah, that's a correct and reasonable answer.  However, can you do it in just a single loop?

I guess I could just do...

int sum1 = 0;
int sum2 = 0;

for(int i = 1; i <= n; i++)
{
     sum1 += i;
     if(i != n)
     {
           sum2 += inputArray[ i - 1];
     }
}

int answer = sum - sum2;

I haven't started working on the second part yet, been too busy, but I am about to do it now.  So, I will let you know shortly lol.

[Tony]

For the second part, if we can "do whatever we want" to the array, can't we just resize it by 1, then iterate the array to find the largest value in the array, and place it in the new spot of the array?  Then make the output array the size of the max number + 1 and initialize all the values to be -1, since they are non-negative numbers, then start placing the numbers in the index of the new array that match its value.  So, if you come across a 42, the number 42 would be put in the 42nd place of the output array.  This would sort the numbers.  Next you can just iterate through the array again and every time you come across a value of -1 you would place that in the outputArray[cnt] where cnt is a count that keeps track of how many -1s you have found.  Since, there will never be more -1s than indexes in the array, you would never get ahead of yourself and overwrite one of the values you have not checked yet.  After you reach the end of the array you can just resize the array back down to the size of cnt+1.  Does that make sense or did I break some rules of the problem?

[William Grim]

For the second part, if we can "do whatever we want" to the array, can't we just resize it by 1, then iterate the array to find the largest value in the array, and place it in the new spot of the array?  Then make the output array the size of the max number + 1 and initialize all the values to be -1, since they are non-negative numbers, then start placing the numbers in the index of the new array that match its value.  So, if you come across a 42, the number 42 would be put in the 42nd place of the output array.  This would sort the numbers.  Next you can just iterate through the array again and every time you come across a value of -1 you would place that in the outputArray[cnt] where cnt is a count that keeps track of how many -1s you have found.  Since, there will never be more -1s than indexes in the array, you would never get ahead of yourself and overwrite one of the values you have not checked yet.  After you reach the end of the array you can just resize the array back down to the size of cnt+1.  Does that make sense or did I break some rules of the problem?

Sorry, when I said that you could do anything you want to the input array, I meant you could read and write to each cell of the array, not resize it.  I didn't mean to be vague, but that would be like creating new variables :-D

You can just assume the output array is length N.  You cannot assume anything in particular about the values in each cell of the output array.  If the cells are initialized with any value, then those cells are set and cannot be changed.

I'll post a solution soon if it's still causing some issues.  You do have the correct general idea though, but think about the fact that you can use the input array's cells for read/write storage and that the numbers are guaranteed to be non-negative (i.e. unsigned).  What can you do with the input array to capture information in a similar fashion as your -1 idea?

[William Grim]

I guess I could just do...

int sum1 = 0;
int sum2 = 0;

for(int i = 1; i <= n; i++)
{
     sum1 += i;
     if(i != n)
     {
           sum2 += inputArray[ i - 1];
     }
}

int answer = sum - sum2;

I haven't started working on the second part yet, been too busy, but I am about to do it now.  So, I will let you know shortly lol.

The original problems states that you only have the input array, your loop counter, and one other variable.  You have a couple variables.

The original problem didn't explicitly state this but should have: the data types you're working with are integers.  However, you seem to have picked up on this.

I'll post a solution this evening after work.

[Tony]

Well, is there no number larger than N?  If there is not, you can just make your array of size N and initialize every value to -1 like I stated before, and then iterate through the array once placing each number in the index that matches that number.  Then when that is done iterate the loop again and each time you read a -1 place it in index value cnt, where cnt is equal to the number of -1s you have found.  At the end you can just place a -1, or a null value for all remaining indexes in the array.  Is that valid?


As for the second part I guess I could just do

int answer = 0;

for(int i = 1; i < n; i++)
{
           answer += i - inputArray[ i];
}

answer += n;  //adds in the final value since there is one less value in the inputArray

return answer;

[William Grim]

Well, is there no number larger than N?  If there is not, you can just make your array of size N and initialize every value to -1 like I stated before, and then iterate through the array once placing each number in the index that matches that number.  Then when that is done iterate the loop again and each time you read a -1 place it in index value cnt, where cnt is equal to the number of -1s you have found.  At the end you can just place a -1, or a null value for all remaining indexes in the array.  Is that valid?

In the original problem, the input array can be 2^N long.  In the second problem, the input array can be N long.

Your algorithm looks like it's on the right track, but the answer I'm looking for is the most efficient in terms of speed and space.  However, I believe I mispoke when I said that the valid range of input values is 1 to 2^N.  I should've either said 1 to (2^N)+1 or 0 to 2^N.  I'm sorry about that.

Since you know that the maximum number is 2^N, you can take advantage of XOR:
Let's assume you have the input array: {4,2,3}.  The missing number would be 1.  This is the algorithm you would follow to find it:

• Shift all numbers by -1, implicitly, leaving you with an implicit array of {3,1,2}.
• Initialize your variable to 0.
• Iterate your array, XOR'ing your variable with the implicit value from the array (see the first step).
• Return your final value + 1 to shift it back to the original offset the array was using.

This is the answer I was hoping you'd get:

Code Select Expand


#include <stdio.h>                                                                                                                                           
                                                                                                                                                             
unsigned findXor(const unsigned const vals[], size_t len) {                                                                                                 
  unsigned val = 0;                                                                                                                                         
  for (int i = 0; i < len; ++i) {                                                                                                                           
    val ^= (vals[i]-1);                                                                                                                                     
  }                                                                                                                                                         
  return val+1;                                                                                                                                             
}                                                                                                                                                           
                                                                                                                                                             
int main() {                                                                                                                                                 
  unsigned vals[] = {1,2,3,4,5,6,7};                                                                                                                         
  size_t n = sizeof(vals) / sizeof(int);                                                                                                                     
  printf("%u\n", findXor(vals, n));                                                                                                                         
  return 0;                                                                                                                                                 
}                                                                                                                                                           


[Tony]

Hmmm, I was thinking about XOR, but wasn't sure if you needed it on this problem.  I was just wondering though, couldn't you just take the input array and XOR it with the value of i as you iterate through the input array?  Then if i = the max range, then just XOR the last number with 0 (essentially XORing the missing number with 0).  Wouldn't that give you the missing value as well?  That will only work for the first one, because there is 1 missing number only.  In the grand scheme of things, you can look at it as if every number was XORed by itself except the missing number.  Right?

[William Grim]

You still need to store your transient value somewhere; so, you may as well just stick to the simpler solution without trying to complicate the algorithm with the loop counter.  I don't think that solution would yield the correct value.

[Justin Camerer]

Tony, do you remember me asking you a question like that in snrprj? I think I got that same question in an interview. That is a good one.

[William Grim]

For the one with K missing numbers, you need to use a bit map.  However, you can't create any variables other than your input array, loop counter, and output array (which is write-once per cell only).  It would also be fair to let you use a constant that knows the bitmask for the sign bit if your unsigned numbers were signed.  I.e. if 7 is the largest value in the input, then your bitmask would be 1000.

You then go through your input array, masking out the MSB and being left with an unsigned number (you have an input array of unsigned to begin, but you'll see why this is important later).  Let your input array be called I and the index i.  You then set the MSB in

Code Select Expand

I[I[i]]

After you are finished setting all the MSBs, traverse the input array again.  Find all the unset MSBs and put those indices in the output array.  You have found the K missing numbers.

[Tony]

Yeah Justin, the one you had was if you have a list of size N but every number is duplicated once, except once.  How can you find that single number in constant time and constant space.  The answer was using XOR also, which is why I was thinking about it for this problem, but didn't quite hit the mark I guess lol.

[blacklee]

A problem from my discrete math class:

You are driving from point A to point B 200 miles apart. You drove first 100 miles with the average speed 25 mph. What should be your speed for the remaining 100 miles in order for the overall average speed of the trip to equal 50 mph?

[William Grim]

A problem from my discrete math class:

You are driving from point A to point B 200 miles apart. You drove first 100 miles with the average speed 25 mph. What should be your speed for the remaining 100 miles in order for the overall average speed of the trip to equal 50 mph?

75 MPH based on a weighted average of "differing distances", which in this case aren't actually different.  I do hope people would get a question like that.

50 = (25 * 100 + x * !00) / 200, solve for x

[CoryLehan]

75 MPH based on a weighted average of "differing distances", which in this case aren't actually different.  I do hope people would get a question like that.

50 = (25 * 100 + x * !00) / 200, solve for x

Not quite right.  Since you'd be travelling 75 mph for 1 hour and 20 minutes and 25 mph for 4 hours, the overall average would be 36 mph.

It's an impossible question.  In order for the average speed to be 50 mph, you would have to get through the entire 200 mile trip in 4 hours (200 miles / 4 hours = 50 mph).  Since the first 100 miles takes the whole 4 hours at 25 mph, it's impossible to average 50 mph.

[William Grim]

Not quite right.  Since you'd be travelling 75 mph for 1 hour and 20 minutes and 25 mph for 4 hours, the overall average would be 36 mph.

It's an impossible question.  In order for the average speed to be 50 mph, you would have to get through the entire 200 mile trip in 4 hours (200 miles / 4 hours = 50 mph).  Since the first 100 miles takes the whole 4 hours at 25 mph, it's impossible to average 50 mph.

You're right.  I did not sanity check.