CareerCup

We can do it by bit logic (E,g, a=4 b=10)
1. Calculate difference b-a (for given e.g. 6)
2. Now calculate ceil(log(b-a+1)(Base 2)) i.e. no of bits required to represent all numbers b/w a and b
3. now call random(0,1) for each bit. (for given example range will be b/w 000 - 111)
4. do step 3 till the number(say num) is less than or equal to 110 i.e. we need only 7 levels since b-a is 6.
5. return num+a.

The binary-search idea is leading to this:
Split the interval of [a, b] into two half and use the first-half if rand() gives 0 and use the 2nd half if it gives 1. Continue this until the size of the interval is 1, and this will be the random number.

Even the splitting (when the size is odd) must use rand() on which mid to use (lower or upper-mid), otherwise (e.g. using always the lower-mid) leads to wrong distribution.

An even better solution is to use real numbers when splitting - until the interval contains only one integer (size of interval becomes less than 2)

public class RandomFunctionEx {
public static void main(String[] args) {
System.out.println(random(4, 8));
}

static int random(int a, int b){
if(b < a)
return -1;
int diff = b - a;
int bits = (int) Math.ceil(Math.log(b-a+1)/Math.log(2));
int sum = findRandom(bits, diff);
return a+sum;
}
static int rand(){
return Math.random() > .5 ? 1 : 0;
}

static int findRandom(int numBits, int diff){
int num = 0;
for(int i = 0 ; i < numBits ; i++){
int x = rand() << i;
num = num | x;
}

if(num > diff){
System.out.println("calling again " + num);
num = findRandom(numBits, diff);
}
return num;
}
}

int random(int a, int b)
{
return(a+rand()/(b-a));
}
//it will return a if rand() generates 0
//it will return b if rand() generates (b-a)*(b-a)

int random(int a, int b)
{
return(a+rand()%(b-a+1));
}

Do something like binary search...

int random (int [] arr, int len)
{
  if (len > 0)
    return arr[random_util(arr, 0, len-1)];
  else 
    ERROR
}

int random_util (int [] arr, int first, int last) 
{
  if (first == last) return first;
  int mid = (first + last)/2;

  if (rand()) {
    return (random_util(arr, mid+1, last));
  } else {
    return (random_util(arr, first, mid));
  }
}

Do something like binary search...

int random (int [] arr, int len)
{
  if (len > 0)
    return arr[random_util(arr, 0, len-1)];
  else 
    ERROR
}

int random_util (int [] arr, int first, int last) 
{
  if (first == last) return first;
  int mid = (first + last)/2;

  if (rand()) {
    return (random_util(arr, mid+1, last));
  } else {
    return (random_util(arr, first, mid));
  }
}

Do something like binary search...

int random (int [] arr, int len)
{
  if (len > 0)
    return arr[random_util(arr, 0, len-1)];
  else 
    ERROR
}

int random_util (int [] arr, int first, int last) 
{
  if (first == last) return first;
  int mid = (first + last)/2;

  if (rand()) {
    return (random_util(arr, mid+1, last));
  } else {
    return (random_util(arr, first, mid));
  }
}

lets b>a
ra = a(1+rand()) //ra >= a
rb = b(1+rand()) //rb >= b

res = (ra+rb)%(b+1)

res would be a when rand() will give 0 //lower limit
res would be b when ra+rb will give b //upper limit
and for others it'll work fine

a + round(rand()*(b-a+1))

algo -
1) Approximate ( b-a ) to the nearest power of 2 .
say b = 3000 , a = 1700 diff = 1300 = 1024 (10 bits ) + 256 (8 bits ) + 16 + 4 .

now generate random numbers within 1024 , 256 , 16 , 4 . ( say w,x,y,z) .

so the random number is a + ( w + x + y + z ) .

modified an answer a lot:

a+(b-a)-(random()*(rand()%(b-a+1))

where rand() is built in function and random is user defined

test case:
a=100
b=250

answer:100+150-0 =250 if random is zero
if random is 1 ans is 100+150 -(1*120)=130
120 generated by built in rand
min will be 100 and max will be 250

Can u please explain the Answers