Count Houses in a Circular Street - Practice Coding Problems

Count Houses in a Circular Street - Problem

Array Interactive Easy

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. 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 openDoor(): Open the door of the house you are in front of.
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.
void moveLeft(): Move to the left house.

Return ans which represents the number of houses on this street.

Input & Output

Example 1 — Mixed Door States

$ Input: street = [true, false, true, false], k = 4

› Output: 4

💡 Note: There are 4 houses in the circular street. We can mark the starting house and count until we return to it.

Example 2 — All Doors Closed

$ Input: street = [false, false, false], k = 10

› Output: 3

💡 Note: All 3 doors are initially closed. We open the first door as a marker, then count 2 more houses before returning to the open door.

Example 3 — Single House

$ Input: street = [true], k = 2

› Output: 1

💡 Note: Only one house in the street. After opening/closing operations, we determine there's exactly 1 house.

Constraints

1 ≤ number of houses ≤ k
k ≤ 10³
Houses are arranged in a circular street

Visualization

Tap to expand

Understanding the Visualization

Input

Circular street with houses having open/closed doors

Process

Use door manipulation to mark position and detect full circle

Output

Total count of houses in the street

Key Takeaway

🎯 Key Insight: Use door manipulation as breadcrumbs to detect when you've walked the full circle

Asked in

M Meta 15 G Google 12

The key insight is to use door states as markers to detect when we've completed a full circle around the street. The optimal approach closes all doors first, then counts houses while opening doors until encountering a closed door. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Close All Then Count	O(n)	O(1)	Close all doors first, then count houses while opening doors until we find a closed one
Mark and Count	O(n)	O(1)	Open the starting door as a marker, then move and count until we return to an open door

Close All Then Count — Algorithm Steps

Step 1: Make one full pass to close all doors
Step 2: Start counting from position 0, opening doors as we go
Step 3: Stop when we encounter a closed door (completed one full circle)

Visualization

Tap to expand

Step-by-Step Walkthrough

Pass 1

Close all doors in the circle

Pass 2

Count houses while opening doors

Complete

Stop when we encounter a closed door

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    bool* houses;
    int size;
    int current;
} Street;

void openDoor(Street* street) {
    street->houses[street->current] = true;
}

void closeDoor(Street* street) {
    street->houses[street->current] = false;
}

bool isDoorOpen(Street* street) {
    return street->houses[street->current];
}

void moveRight(Street* street) {
    street->current = (street->current + 1) % street->size;
}

void moveLeft(Street* street) {
    street->current = (street->current - 1 + street->size) % street->size;
}

int solution(Street* street, int k) {
    // First pass: close all doors
    for (int i = 0; i < k; i++) {
        closeDoor(street);
        moveRight(street);
        if (isDoorOpen(street)) {
            break;
        }
    }
    
    // Reset and count
    closeDoor(street);
    int count = 0;
    
    // Second pass: count while opening doors
    while (!isDoorOpen(street)) {
        count++;
        openDoor(street);
        moveRight(street);
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int k;
    scanf("%d", &k);
    
    // Parse boolean array (simplified)
    bool houses[100];
    int size = 0;
    char* token = strtok(line, ",");
    while (token != NULL && size < 100) {
        if (strstr(token, "true") != NULL) {
            houses[size] = true;
        } else {
            houses[size] = false;
        }
        size++;
        token = strtok(NULL, ",");
    }
    
    Street street = {houses, size, 0};
    int result = solution(&street, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through n houses, still linear time complexity

✓ Linear Growth

Space Complexity

O(1)

Only using a counter variable, no extra data structures

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

842 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

Close All Then Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler