4

I have on one random number generator which generates number between 1 to k. Also i have array of int type (i.e int[]) ,whose size is N , where k is smaller than N .

Now problem is i need to save unique generated numbers into array (rejecting the generated duplicate number) and has to maintain order of generated numbers , without using any extra space and in O(N) complexity. i.e i same array i need to maintain order of generated number also. So that i can retrieve them in generated order. No bitmap or extra array etc is suppose to use.

Its not a homework. Its one of the interview question. I am not supposed to use any extra space. He asked me to use the fact that k is smaller than N and you need to inculcate the behavior of hashmap in same array. I proposed many algorithms using extra spaces but he rejected also using sorting , but i was not able to maintain generated order.

Trying
  • 14,004
  • 9
  • 70
  • 110
KCS
  • 2,937
  • 4
  • 22
  • 32
  • If I were you, I'd 1) save my elements to a sorted list, and 2) call toArray() when I'm done. http://stackoverflow.com/questions/4031572/sorted-array-list-in-java. PS: This sounds like homework? – paulsm4 Nov 21 '13 at 02:19
  • 1
    Can you show us what code you have so far? What approach(s) are you considering? – Elliott Frisch Nov 21 '13 at 02:20
  • "*without using any extra space*" seems like impossible task. Even for swapping you need `int temp` that takes 4 bytes. – PM 77-1 Nov 21 '13 at 02:25
  • "*same array need to maintain order of generated numbers also*" Another impossible task since array can have only one *order*. – PM 77-1 Nov 21 '13 at 02:27
  • @PM77-1: "without using any extra space" usually refers to not creating an array which length depends on the input, in other words, using `O(1)` additional space is ok. In his statement "same array I need to maintain order of generated numbers also", OP is a bit vague, I agree, but he obviously only one order here if you read the whole question carefully, the order for which the random numbers are generated. – justhalf Nov 21 '13 at 02:31

1 Answers1

5

OK, I'll buy this isn't homework. Here's the solution. Suppose k=3, N=5

Start:

ar[0] = 0
ar[1] = 0
ar[2] = 0
ar[3] = 0
ar[4] = 0

Generate a random number. Suppose it's 2. We need to store two bits of information now:

  • "2" is the first random number.
  • "2" is taken.

So we do this:

ar[0] = 2
ar[1] = 0
ar[2] = 10  // 10 is any number that's larger than N.
ar[3] = 0
ar[4] = 0

next number: 4

ar[0] = 2
ar[1] = 4
ar[2] = 10  // taken
ar[3] = 0
ar[4] = 10  // taken

next number: 2

ar[2] >= 10 thus taken, try another number

next number: 1

ar[0] = 2
ar[1] = 14  // added 10 to signify it's taken
ar[2] = 11  // added 1 as it's the current number
ar[3] = 0
ar[4] = 10  // taken

Done.

Now, iterate through array, and subtract 10 from everything that's larger than 10. you'll end up with 

ar[0] = 2
ar[1] = 4
ar[2] = 1
ar[3] = 0
ar[4] = 0

One caveat - this assumes random numbers are in [1..N] range. if they are [0..N-1], you'd have to tweak a bit.

iluxa
  • 6,941
  • 18
  • 36
  • Does such algorithm have a name? – PM 77-1 Nov 21 '13 at 02:30
  • @iluxa: Probably you meant to add `N*2` instead of `k*2`. Adding `k*2` will result in ambiguity whether the number has already been taken or it's just a number being generated as such (for example for `k=2`, and `array[1] = 5`, you don't know whether it's actually really number 5 with no `1` has been generated, or that it's a 1 with `1` has been generated. Using `N*2` (actually `N` suffices), you can check whether the number is greater than `N`, then subtract `N` from it if it is. This algorithm will be correct since the max value is `N`, so anything > `N` is a sign that something was there. – justhalf Nov 21 '13 at 02:35
  • generated numbers only go up to k, so i ~think~ k+1 would suffice. But hey, N*2 + 1000000 for good merit – iluxa Nov 21 '13 at 02:38
  • Generated numbers can go to `N`. `k` is the number of random numbers to be generated. Anyway, I guess negating the number will be better, it's more intuitive =D – justhalf Nov 21 '13 at 02:39
  • 3
    @PM 77-1: "the famous iluxa algorithm for solving a random homework" i suppose :) – iluxa Nov 21 '13 at 02:39
  • Oh no, you can't negate zero in uninitialized parts of the array, haha. Sorry, we need your `+N` method then – justhalf Nov 21 '13 at 02:40
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/41576/discussion-between-justhalf-and-iluxa) – justhalf Nov 21 '13 at 02:41