Generate Random Point in a Circle - Practice Coding Problems

Generate Random Point in a Circle - Problem

Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle.

Implement the Solution class:

Solution(double radius, double x_center, double y_center) initializes the object with the radius of the circle radius and the position of the center (x_center, y_center).
randPoint() returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array [x, y].

Input & Output

Example 1 — Unit Circle at Origin

$ Input: radius = 1.0, x_center = 0.0, y_center = 0.0

› Output: [0.52, -0.85] (example output)

💡 Note: Generate a random point inside unit circle centered at origin. The actual output will vary each time due to randomness, but will always satisfy x² + y² ≤ 1.

Example 2 — Larger Circle with Offset Center

$ Input: radius = 5.0, x_center = 3.0, y_center = 4.0

› Output: [6.2, 1.8] (example output)

💡 Note: Generate random point in circle of radius 5 centered at (3,4). Point satisfies (x-3)² + (y-4)² ≤ 25.

Example 3 — Small Circle

$ Input: radius = 0.1, x_center = -1.0, y_center = 2.0

› Output: [-0.95, 2.03] (example output)

💡 Note: Very small circle shows the algorithm works for any radius size. Point is within 0.1 units of center (-1, 2).

Constraints

0 < radius ≤ 10⁸
-10⁷ ≤ x_center, y_center ≤ 10⁷
At most 3 × 10⁴ calls will be made to randPoint

Visualization

Tap to expand

Understanding the Visualization

Input

Circle defined by radius and center coordinates

Process

Generate uniform random point using mathematical transformation

Output

Random [x,y] coordinates inside the circle

Key Takeaway

🎯 Key Insight: Use square root transformation on radius to achieve uniform distribution across circle area

Asked in

G Google 12 f Facebook 8 a Amazon 6 M Microsoft 4

The key insight is that uniform random sampling in a circle requires careful handling of the radius distribution. The polar coordinate approach with √(random) radius scaling ensures uniform area distribution. Best approach uses mathematical transformation: Time O(1), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Rejection Sampling	O(1)	O(1)	Generate random points in a square until one falls inside the circle
Polar Coordinate Transform	O(1)	O(1)	Use polar coordinates with proper radius transformation for uniform distribution

Rejection Sampling — Algorithm Steps

Generate random x in [-radius, radius]
Generate random y in [-radius, radius]
Check if x² + y² ≤ radius²
If valid, translate to actual center and return
Otherwise repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Square

Create random point in bounding square

Distance Check

Test if point is within circle radius

Accept/Reject

Keep valid points, discard invalid ones

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef struct {
    double radius;
    double x_center;
    double y_center;
} Solution;

Solution* createSolution(double radius, double x_center, double y_center) {
    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->radius = radius;
    sol->x_center = x_center;
    sol->y_center = y_center;
    srand(time(NULL));
    return sol;
}

void randPoint(Solution* sol, double* result) {
    while (1) {
        double x = ((double)rand() / RAND_MAX) * 2 * sol->radius - sol->radius;
        double y = ((double)rand() / RAND_MAX) * 2 * sol->radius - sol->radius;
        if (x * x + y * y <= sol->radius * sol->radius) {
            result[0] = sol->x_center + x;
            result[1] = sol->y_center + y;
            break;
        }
    }
}

int main() {
    double radius, x_center, y_center;
    scanf("%lf %lf %lf", &radius, &x_center, &y_center);
    
    Solution* sol = createSolution(radius, x_center, y_center);
    double result[2];
    randPoint(sol, result);
    printf("[%f,%f]\n", result[0], result[1]);
    
    free(sol);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Expected constant time, though worst case could be infinite

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables for coordinates and calculations

✓ Linear Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Rejection Sampling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler