We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Houses in a Circular Street

Number: 2875

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

You are given a circular street of houses with an unknown total number n (with 1 <= n <= k) and an upper bound k on the number of houses. Each house’s door may be open or closed initially. You can interact with the street via the provided functions: • openDoor(): Open the door of the current house. • closeDoor(): Close the door of the current house. • isDoorOpen(): Check if the current house’s door is open. • moveRight(): Move to the next house to the right. • moveLeft(): Move to the next house to the left. Starting from an arbitrary house, your task is to count the total number of houses on the circular street.

Key Insights

  • Since the street is circular and you do not know the number of houses n, you must detect when you have completed a full cycle.
  • Directly comparing door states is tricky because houses may naturally be open or closed.
  • A two‑pass approach is effective: first “normalize” the street (i.e. force every door to a known state) and then traverse the street to mark your starting house.
  • By setting all doors to a standard state (closed) and then marking a single house (by opening its door), you can later travel until you encounter that marker again—at which point you have completed a full circle.

Space and Time Complexity

Time Complexity: O(k) – the normalization phase takes k steps (using the maximum bound) and the counting phase takes at most n steps (with n ≤ k).
Space Complexity: O(1) – only a few counters and constant extra memory are used.

Solution

The solution uses a two-phase process:

  1. Normalize the street: Traverse k steps and ensure every house is set to a closed door state. Because k is an upper bound (n ≤ k), this guarantees that every house will eventually be visited (possibly more than once if k > n).

  2. Mark and count: Pick the current house as the starting marker by opening its door. Then move right and for each new house that is closed, mark it (by opening its door) and increment the count. Continue until you encounter a house whose door is already open (the marker you set at the start). At that point, you have completed a full rotation and the count is the number of houses.

Each implementation uses the interactive functions provided by the Street class. This approach avoids any ambiguity due to initial door states and leverages the allowed operations to detect when the cycle is complete.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed line-by-line comments.

class Solution:
    def countHouses(self, street, k):
        # Phase 1: Normalize the street by closing every door.
        # Iterate exactly k times because k is the maximum bound on the number of houses.
        for i in range(k):
            if street.isDoorOpen():
                # If the door is open, close it so that all doors will be uniform.
                street.closeDoor()
            # Move to the next house on the right.
            street.moveRight()
        
        # Phase 2: Mark a starting house and count all houses.
        # The current house becomes our starting house; mark it by opening its door.
        street.openDoor()  
        count = 1  
        # Move to the next house.
        street.moveRight()
        
        # Continue traversing until we encounter the marked House again.
        while not street.isDoorOpen():
            # Mark the current house (visited) by opening its door.
            street.openDoor()
            count += 1
            # Move to the next house.
            street.moveRight()
        
        # When the loop stops, we have encountered the starting marker.
        # Therefore, 'count' is equal to the total number of houses on the street.
        return count
← Back to All Questions