Count houses in a circular street ii

62.0% acceptance

Mar 31, 2026

You are given an object street of class Street that represents a circular street and a positive integer k which represents a maximum bound for the number of houses in that street (in other words, the number of houses is less than or equal to k). Houses' doors could be open or closed initially (at least one is open). Initially, you are standing in front of a door to a house on this street. Your task is to count the number of houses in the street. The class Street contains the following functions which may help you: void closeDoor(): Close the door of the house you are in front of. boolean isDoorOpen(): Returns true if the door of the current house is open and false otherwise. void moveRight(): Move to the right house. Note that by circular street, we mean if you number the houses from 1 to n, then the right house of housei is housei+1 for i < n, and the right house of housen is house1. Return ans which represents the number of houses on this street.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/**
 * Definition for a street.
 * impl Street {
 *     pub fn new(doors: Vec<i32>) -> Self {}
 *     pub fn close_door(&mut self) {}
 *     pub fn is_door_open(&self) -> bool {}
 *     pub fn move_right(&mut self) {}
 * }
 */
impl Solution {
  pub fn house_count(street: Street, k: i32) -> i32 {
    let mut street = street;
    let k = k as usize;
    // Phase 1: Read 2k states without modification
    let mut seq = Vec::with_capacity(2 * k);
    for _ in 0..2 * k {
      seq.push(street.is_door_open());
      street.move_right();
    }
    // Find an open door and close it (breaks internal periodicity)
    while !street.is_door_open() {
      street.move_right();
    }
    street.close_door();
    // Phase 2: Read 2k states after modification (need >= 2 periods for KMP)
    let mut seq2 = Vec::with_capacity(2 * k);
    for _ in 0..2 * k {
      street.move_right();
      seq2.push(street.is_door_open());
    }
    // Use lcm of both periods: seq captures the unmodified pattern, seq2 captures
    // the modified pattern. Their lcm always equals n even when closing one door
    // creates an apparent shorter period in seq2 (e.g. [1,1,0,1] -> [0,1,0,1], period 2 vs 4).
    let p1 = Self::find_period(&seq);
    let p2 = Self::find_period(&seq2);
    Self::lcm(p1, p2) as i32
  }

  fn gcd(a: usize, b: usize) -> usize {
    if b == 0 { a } else { Self::gcd(b, a % b) }
  }

  fn lcm(a: usize, b: usize) -> usize {
    a / Self::gcd(a, b) * b
  }

  fn find_period(s: &[bool]) -> usize {
    let len = s.len();
    let mut fail = vec![0usize; len];
    for i in 1..len {
      let mut j = fail[i - 1];
      while j > 0 && s[i] != s[j] {
        j = fail[j - 1];
      }
      if s[i] == s[j] {
        j += 1;
      }
      fail[i] = j;
    }
    len - fail[len - 1]
  }
}