Random 7 from Random 5 - CS Interviewing

math

probability

rejectionsampling

# Random 7 from Random 5

## Difficulty
Medium

## Tags
`math`, `probability`, `rejection sampling`

## Problem Statement
Given a function `rand5()` that generates a uniformly random integer in the range [1, 5], implement a function `rand7()` that generates a uniformly random integer in the range [1, 7].

You may only use `rand5()` as your source of randomness.

## Constraints
- `rand5()` returns each integer 1-5 with probability 1/5.
- `rand7()` must return each integer 1-7 with probability 1/7.
- Minimize the expected number of calls to `rand5()`.

## Signatures
### Python
```python
def rand5() -> int:
    pass
```

### Java
```java
public class Solution {
    public int rand5() {
        return null;
    }
}
```

### Csharp
```csharp
public class Solution {
    public int rand5() {
        throw new NotImplementedException();
    }
}
```

### Cpp
```cpp
class Solution {
public:
    int rand5() {
        
    }
};
```

### C
```c
int rand5() {
    
}
```

### Ruby
```ruby
def rand5()
    
end
```

### Perl
```perl
sub rand5 {
    my ($self, @args) = @_;
    
}
```

### Scala
```scala
object Solution {
    def rand5(): Int = {
        
    }
}
```

### Haskell
```haskell
rand5 :: ... -> ...
rand5 args = undefined
```

### Clojure
```clojure
(defn rand5 []
  )
```

### Scheme
```scheme
(define (rand5 )
  )
```

## Examples
### Example 1
**Output Distribution (over many calls):**
```
1: ~14.28%
2: ~14.28%
3: ~14.28%
4: ~14.28%
5: ~14.28%
6: ~14.28%
7: ~14.28%
```

## Hints
### Rejection Sampling Approach
1. Generate a number in a larger range that's divisible by 7.
2. Use `5 * (rand5() - 1) + rand5()` to generate numbers 1-25 uniformly.
3. If the number is ≤ 21, map it to 1-7 using modulo.
4. If the number is 22-25, reject and retry.

### Algorithm
```python
def rand7():
    while True:
        # Generate 1-25 uniformly
        num = 5 * (rand5() - 1) + rand5()
        if num <= 21:
            return 1 + (num - 1) % 7
        # Reject 22-25 and retry
```

### Expected Calls
- Probability of success: 21/25 = 84%
- Expected calls to rand5(): 2 / 0.84 ≈ 2.38 per rand7() call

Please log in to view the solution editor and submit code.