CareerCup

between a and b, I assume a half open interval [a, b)

question is the distribution, if it should be normal, the previous posts are probably right (needs a prove though). If we want uniform distribution things are different.

I could create a random function that creates a uniform random number in the range [0 and 2^n) by applying the given function to each bit. Then I could use this new function to create a random number in the range [0, 2^n) where n would be lg2(b-a) + 1. If the random number exceeds b-a, I try again, if not, I add it to a and return the result.

#include <iostream>
#include <unordered_map>

using namespace std;

bool Rand2()
{
	return rand() % 2;
}

uint32_t RandAB(uint32_t a, uint32_t b)
{
	uint32_t max_val = b - a;

	int bits = 0;
	for (uint32_t mask = 1; mask <= max_val && mask != 0; mask <<= 1) {
		++bits;
	}

	uint32_t rnd = 0;
	do {
		rnd = 0;
		for (int i = 0; i < bits; ++i) {
			rnd <<= 1;
			rnd |= Rand2();
		}
	} while (rnd > max_val);

	return a + rnd;
}

int main()
{
	srand(time(NULL));
	unordered_map<uint32_t, int> stats;
	for (int i = 0; i < 100000000; ++i) {
		++stats[RandAB(3, 14)];
	}
	for (auto &el : stats) {
		cout << el.second << "=>" << el.first << "\n";
	}
}

random function for every bit
or
rand + 2 * rand + 4*rand + ...
you can see that rand + 2 *rand output 0 1 2 3 uniformly

Here is my Solution:

```
public void random(int a, int b) {
int num = 1<<31;
int min=num|a;
int max=num|b;

StringBuilder sb=new StringBuilder("");
String minStr=Integer.toBinaryString(min);
String maxStr=Integer.toBinaryString(max);
int idx=1;
while (idx< maxStr.length()){
if(minStr.charAt(idx)!=maxStr.charAt(idx)) break;
sb.append(minStr.charAt(idx));
idx++;
}

int temp=idx;
while (true){
while (idx<maxStr.length()){
String r=rand();
sb.append(r);
idx++;
}

if((Integer.parseInt(sb.toString(),2) >=a &&
Integer.parseInt(sb.toString(),2)<=b)){
System.out.println(Integer.parseInt(sb.toString(),2));
break;
}
sb.delete(temp-1,sb.length());
idx=temp;
}
}

private String rand() {
Random rd = new Random(); // creating Random object
return !rd.nextBoolean() ? "0" : "1";
}
```

Let's call this function rand();

int randomNumber = a-1;
for(int i = 0; i < b-a; i++){
	if rand() = 0
		randomNumber++;
}

Let's assume the function that randomly returns 1 or 0 is called rand() and is defined in the same class.

public int randBetweenAandB(int a, int b){
int r = a-1;
for(int i = 0; i < b-a; i++){
	if(rand() == 1)
		r++;
}


return r;

}