Direction assignments with exactly k visible people

35.7% acceptance

Mar 31, 2026

You are given three integers n, pos, and k. There are n people standing in a line indexed from 0 to n - 1. Each person independently chooses a direction: 'L': visible only to people on their right 'R': visible only to people on their left A person at index pos sees others as follows: A person i < pos is visible if and only if they choose 'L'. A person i > pos is visible if and only if they choose 'R'. Return the number of possible direction assignments such that the person at index pos sees exactly k people. Since the answer may be large, return it modulo 109 + 7.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_visible_people(n: i32, pos: i32, k: i32) -> i32 {
    let m = 1_000_000_007i64;
    let left = pos as i64;       // people to left of pos
    let right = (n - 1 - pos) as i64; // people to right of pos
    let k = k as i64;
    let total = left + right;
    
    if k > total {
      return 0;
    }
    
    // Person at pos sees:
    // - Among left people: those who chose 'L'
    // - Among right people: those who chose 'R'
    // Person at pos can choose either direction (doesn't affect count).
    // So factor of 2 for pos's own choice.
    // We need j people from left choosing 'L' and (k-j) people from right choosing 'R'.
    // For each j from 0..=min(k, left):
    //   C(left, j) * C(right, k-j) * 2^(left-j) ... wait no.
    //   The remaining left-j people must choose 'R' (or can choose anything?).
    //   No - each person independently chooses L or R. We need exactly j out of left to choose L
    //   AND exactly k-j out of right to choose R. The remaining left-j choose R, remaining right-(k-j) choose L.
    //   So it's C(left, j) * C(right, k-j) for each j.
    // Then multiply by 2 for pos's choice.
    
    // Precompute factorials
    let max_n = n as usize + 1;
    let mut fact = vec![1i64; max_n];
    for i in 1..max_n {
      fact[i] = fact[i - 1] * i as i64 % m;
    }
    let mut inv_fact = vec![1i64; max_n];
    inv_fact[max_n - 1] = Self::mod_pow(fact[max_n - 1], m - 2, m);
    for i in (0..max_n - 1).rev() {
      inv_fact[i] = inv_fact[i + 1] * (i + 1) as i64 % m;
    }
    
    let comb = |n: i64, r: i64| -> i64 {
      if r < 0 || r > n {
        return 0;
      }
      fact[n as usize] * inv_fact[r as usize] % m * inv_fact[(n - r) as usize] % m
    };
    
    let mut ans = 0i64;
    for j in 0..=k.min(left) {
      let rem = k - j;
      if rem > right {
        continue;
      }
      ans = (ans + comb(left, j) * comb(right, rem) % m) % m;
    }
    
    ans = ans * 2 % m;
    ans as i32
  }
  
  fn mod_pow(mut base: i64, mut exp: i64, m: i64) -> i64 {
    let mut result = 1i64;
    base %= m;
    while exp > 0 {
      if exp & 1 == 1 {
        result = result * base % m;
      }
      exp >>= 1;
      base = base * base % m;
    }
    result
  }
}