CODEWITHSUNDEEP
javaalgorithmhashtable
XIAOAGE
XIAOAGE

Reputation: 35

Calculating the occurrence of a random number

I would like to calculate the occurrence of a random number. I will pick 1,000,000 numbers randomly from 1 to 1,000,000,000.

For example: When I enter 1000, it will show how many times that 1000 has occurred in these 1,000,000 numbers.

Following is the code I wrote, but I don't know why it always outputs 0. Could you help me fix the code?

I made a hash table and put linked lists in it to avoid exceptions because with 1,000,000,000 the program runs out of memory.

public static void main(String[] args) {

    Hashtable<Integer,LinkedList<Integer>> map
            = new Hashtable<Integer,LinkedList<Integer>>();

    int index;
    int b;
    int x;

    for (b=0; b<1000000; b++){
        x = (int) (Math.random()*1000000000)+1;
        index = x % 10000;

        if(map.get(index) == null){
            map.put(index, new LinkedList<Integer>());
            map.get(index).add(x);
        }else{
            map.get(index).add(x);
        }
    }

Upvotes: 2

Views: 185

Answers (1)

ADTC
ADTC

Reputation: 10086

Your code is probably working fine. Here is why.

Statistics using your description

1,000,000 numbers randomly from 1 to 1,000,000,000
how many times that 1000 has occurred

The chance that a random number picked between 1 to 1,000,000,000 to be a particular number like 1,000 is:

      1
------------- = 0.000 000 001 (very close to zero)
1,000,000,000

If you do it 1,000,000 times, the chances are:

0.000 000 001 * 1,000,000 = 0.001 (still pretty close to zero)

To get to 1, you'll have to multiply by 1,000 again.

What this means is that, with a program written to match your description, you'll have to run it a thousand times to ensure that you'll see the particular number 1,000 appearing at least once.

Statistics using your code snippet

Your actual code snippet does not seem to match your description. So let us look at it separately.

for (b=0; b<1000000; b++){
    x = (int) (Math.random()*1000000000)+1;
    index = x % 10000;

The % sign is modulus, which gives 0 for when a number x is perfectly divisible by 10,000 (note: not 1,000). It is not clear what you are doing with this modulus value after using it as an index, but I'll just assume that after the loop is done, you'll get the count for index = 0.

Assuming this is the case, the numbers from 1 to 1,000,000,000 that qualify for x % 10000 = 0 are:

10000, 20000, 30000, .... 999990000, 1000000000

There are 100,000 such numbers. The odds of getting any one of them as a random number once is:

   100,000
------------- = 0.0001 (pretty close to zero)
1,000,000,000

Since you're repeating it for 1,000,000 times, the odds of getting x % 10000 = 0 are:

0.0001 * 1,000,000 = 100 (very very good!)

This means, if you do map.get(0).size() you should get the value somewhere around 100.

Reality check

I gave it a test run on Ideone. In fact, I got the following results for a few runs. I also plugged in map.get(1000) just for the heck of it.

For map.get(0),    size is 92
For map.get(1000), size is 106

For map.get(0),    size is 113
For map.get(1000), size is 92

For map.get(0),    size is 104
For map.get(1000), size is 86

For map.get(0),    size is 111
For map.get(1000), size is 103

Upvotes: 4

Related Questions