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 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.

Examples

Example 1:

1
2
3
4

Input: street = [1,1,1,1], k = 10
Output: 4
Explanation: There are 4 houses, and all their doors are open. 
The number of houses is less than k, which is 10.

Example 2:

1
2
3
4

Input: street = [1,0,1,1,0], k = 5
Output: 5
Explanation: There are 5 houses, and the doors of the 1st, 3rd, and 4th house (moving in the right direction) are open, and the rest are closed.
The number of houses is equal to k, which is 5.

Constraints:

  • n == number of houses
  • 1 <= n <= k <= 10^5
  • street is circular by definition provided in the statement.
  • The input is generated such that at least one of the doors is open.
Similar Problems

Solution

Method 1 – Mark and Move (Simulation, Only Close)

Intuition

Since the street is circular and at least one door is open, we can close each open door as we visit it, moving right each time. When we return to a house with a closed door, we’ve completed a full circle and counted all houses.

Approach

  1. Start at the initial house. If the door is open, close it and increment the count.
  2. Move right and repeat: if the door is open, close it and increment the count.
  3. Stop when you return to a house with a closed door (the starting house after a full circle).
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * // This is the Street's API interface.
 * class Street {
 * public:
 *     void closeDoor();
 *     bool isDoorOpen();
 *     void moveRight();
 * };
 */
class Solution {
public:
    int houseCount(Street* street, int k) {
        int cnt = 0;
        if (street->isDoorOpen()) {
            street->closeDoor();
            cnt++;
        }
        for (int i = 1; i < k; ++i) {
            street->moveRight();
            if (street->isDoorOpen()) {
                street->closeDoor();
                cnt++;
            } else {
                break;
            }
        }
        return cnt;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// The Street API is provided by the platform. We declare the interface here
// for documentation purposes and implement the same logic as other languages.
type Street interface {
    CloseDoor()
    IsDoorOpen() bool
    MoveRight()
}

// houseCount returns the number of houses in the circular street.
func houseCount(street Street, k int) int {
    cnt := 0
    if street.IsDoorOpen() {
        street.CloseDoor()
        cnt++
    }
    for i := 1; i < k; i++ {
        street.MoveRight()
        if street.IsDoorOpen() {
            street.CloseDoor()
            cnt++
        } else {
            break
        }
    }
    return cnt
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * // This is the Street's API interface.
 * class Street {
 *     void closeDoor();
 *     boolean isDoorOpen();
 *     void moveRight();
 * }
 */
class Solution {
    public int houseCount(Street street, int k) {
        int cnt = 0;
        if (street.isDoorOpen()) {
            street.closeDoor();
            cnt++;
        }
        for (int i = 1; i < k; i++) {
            street.moveRight();
            if (street.isDoorOpen()) {
                street.closeDoor();
                cnt++;
            } else {
                break;
            }
        }
        return cnt;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// The Street API is provided by the platform; signature shown for clarity.
interface Street {
    fun closeDoor()
    fun isDoorOpen(): Boolean
    fun moveRight()
}

class Solution {
    fun houseCount(street: Street, k: Int): Int {
        var cnt = 0
        if (street.isDoorOpen()) {
            street.closeDoor()
            cnt++
        }
        for (i in 1 until k) {
            street.moveRight()
            if (street.isDoorOpen()) {
                street.closeDoor()
                cnt++
            } else {
                break
            }
        }
        return cnt
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# This is the Street's API interface.
# class Street:
#     def closeDoor(self):
#     def isDoorOpen(self) -> bool:
#     def moveRight(self):
class Solution:
    def houseCount(self, street: 'Street', k: int) -> int:
        cnt = 0
        if street.isDoorOpen():
            street.closeDoor()
            cnt += 1
        for _ in range(1, k):
            street.moveRight()
            if street.isDoorOpen():
                street.closeDoor()
                cnt += 1
            else:
                break
        return cnt
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


// The Street trait is shown for documentation; the platform provides an
// implementation when running on the judge.
pub trait Street {
    fn closeDoor(&mut self);
    fn isDoorOpen(&self) -> bool;
    fn moveRight(&mut self);
}

pub struct Solution;

impl Solution {
    pub fn house_count(street: &mut dyn Street, k: i32) -> i32 {
        let mut cnt = 0;
        if street.isDoorOpen() {
            street.closeDoor();
            cnt += 1;
        }
        for _ in 1..k {
            street.moveRight();
            if street.isDoorOpen() {
                street.closeDoor();
                cnt += 1;
            } else {
                break;
            }
        }
        cnt
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


// The Street interface is provided by the platform; we declare it here
// for documentation and type-checking within the note.
interface Street {
    closeDoor(): void;
    isDoorOpen(): boolean;
    moveRight(): void;
}

class Solution {
    public houseCount(street: Street, k: number): number {
        let cnt = 0;
        if (street.isDoorOpen()) {
            street.closeDoor();
            cnt++;
        }
        for (let i = 1; i < k; i++) {
            street.moveRight();
            if (street.isDoorOpen()) {
                street.closeDoor();
                cnt++;
            } else {
                break;
            }
        }
        return cnt;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of houses, as we may visit each house once.
  • 🧺 Space complexity: O(1), only a constant amount of space is used.