Count Houses in a Circular Street II - Practice Coding Problems

Count Houses in a Circular Street II - Problem

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 house_i is house_i+1 for i < n, and the right house of house_n is house₁.

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

Input & Output

Example 1 — Mixed Open/Closed Doors

$ Input: houses = [true,false,true,true], k = 10

› Output: 4

💡 Note: There are 4 houses in the circular street. Close the starting door, then walk right counting houses until we return to the closed door.

Example 2 — All Doors Open

$ Input: houses = [true,true,true], k = 4

› Output: 3

💡 Note: 3 houses total. Close starting door, move right 3 times counting, then encounter the closed door we marked.

Example 3 — Large Street

$ Input: houses = [true,false,true,false,true,true,false], k = 20

› Output: 7

💡 Note: 7 houses in the circular street. Our algorithm finds the exact count regardless of k value.

Constraints

n == number of houses
1 ≤ n ≤ k ≤ 10³
At least one door is initially open

Visualization

Tap to expand

Understanding the Visualization

Input

Circular street with mixed open/closed doors

Process

Use door states to detect complete traversal

Output

Exact count of houses in the street

Key Takeaway

🎯 Key Insight: Use door states as breadcrumbs - close the starting door and walk until you return to it

Asked in

G Google 12 F Facebook 8 M Microsoft 6

The key insight is to use door states as markers to detect when we've completed a full circle. The optimal Mark and Return Strategy closes the starting door and walks right until returning to it, giving us the exact house count in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Multiple Complete Traversals	O(k)	O(1)	Walk around the street k times to ensure we count all houses
Mark and Return Strategy	O(n)	O(1)	Close the starting door and walk until we return to it

Multiple Complete Traversals — Algorithm Steps

Move right k times
Count each move as one house
Return k as the total count

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at position 0

Move K Times

Move right k times, counting each step

Result

Return k as house count

Code -

solution.c — C

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

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

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

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

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

int solution(Street* street, int k) {
    int count = 0;
    for (int i = 0; i < k; i++) {
        moveRight(street);
        count++;
    }
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(k)

We move right exactly k times regardless of actual house count

✓ Linear Growth

Space Complexity

O(1)

Only using a counter variable, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

246 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

Multiple Complete Traversals — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler