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.

Improve this question
5
  • If I were you, I'd 1) save my elements to a sorted list, and 2) call toArray() when I'm done. stackoverflow.com/questions/4031572/sorted-array-list-in-java. PS: This sounds like homework? Commented Nov 21, 2013 at 2:19
  • 1
    Can you show us what code you have so far? What approach(s) are you considering? Commented Nov 21, 2013 at 2:20
  • "without using any extra space" seems like impossible task. Even for swapping you need int temp that takes 4 bytes. Commented Nov 21, 2013 at 2:25
  • "same array need to maintain order of generated numbers also" Another impossible task since array can have only one order. Commented Nov 21, 2013 at 2: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. Commented Nov 21, 2013 at 2:31

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Does such algorithm have a name?
@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.
generated numbers only go up to k, so i ~think~ k+1 would suffice. But hey, N*2 + 1000000 for good merit
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
@PM 77-1: "the famous iluxa algorithm for solving a random homework" i suppose :)
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.