Teaching Kids Programming – Algorithms to Count Houses in a Circular Street (with Restrictions – at least one door open)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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. Example 1: 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: 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 <= 105 street is circular by definition provided in the statement. The input is generated such that at least one of the doors is open.

Algorithms to Count Houses in a Circular Street (with Restrictions)

Compare to Teaching Kids Programming – Algorithms to Count Houses in a Circular Street, this removes the usage of three methods: openDoor(), isDoorClose(), and moveLeft(). Also, we are given that at least one door is open (this is very important as we need to move to a door which is open).

IsDoorOpen() and IsDoorClose() is basically the same thing – only one method is required, and having two isn’t necessary.

If we go with one direction only – we can go around the circle, so moveLeft or moveRight doesn’t matter. Since

We move to a door which is open:

1
2

while not street.isDoorOpen():
    street.moveRight()

while not street.isDoorOpen():
    street.moveRight()

If all doors are closed, then above loop will go endlessly. Since, the upper bound of the number of the houses is k, then we can iterate k times, so that we can definitely go around one cycle/circle.

1
2
3
4
5
6

atLeastOneDoorOpen = False
for _ in range(k):
    if s.isDoorOpen():
        atLeastOneDoorOpen = True
        break
    s.moveRight()

atLeastOneDoorOpen = False
for _ in range(k):
    if s.isDoorOpen():
        atLeastOneDoorOpen = True
        break
    s.moveRight()

Once we are at the first open door, we can move right, and check the door open, if it is open, we update the distance and close it. If we are repeating this k times, we will go back to the first door and no more after that. The number of the houses equal to the distance plus one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# Definition for a street.
# class Street:
#     def closeDoor(self):
#         pass
#     def isDoorOpen(self):
#         pass
#     def moveRight(self):
#         pass
class Solution:
    def houseCount(self, s: Optional['Street'], k: int) -> int:
        for _ in range(k):
            if s.isDoorOpen():
                break
            s.moveRight()
        ans = 0
        for i in range(k):
            s.moveRight()
            if s.isDoorOpen():
                ans = i + 1
                s.closeDoor()
        return ans

# Definition for a street.
# class Street:
#     def closeDoor(self):
#         pass
#     def isDoorOpen(self):
#         pass
#     def moveRight(self):
#         pass
class Solution:
    def houseCount(self, s: Optional['Street'], k: int) -> int:
        for _ in range(k):
            if s.isDoorOpen():
                break
            s.moveRight()
        ans = 0
        for i in range(k):
            s.moveRight()
            if s.isDoorOpen():
                ans = i + 1
                s.closeDoor()
        return ans

Another idea is to track the first open door and the last open door:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Definition for a street.
# class Street:
#     def closeDoor(self):
#         pass
#     def isDoorOpen(self):
#         pass
#     def moveRight(self):
#         pass
class Solution:
    def houseCount(self, s: Optional['Street'], k: int) -> int:
        firstOpen = None
        lastOpen = 0
        d = 0
        while d - lastOpen <= k:
            if s.isDoorOpen():
                if not firstOpen:
                    firstOpen = d
                lastOpen = d
                if firstOpen != lastOpen:
                    s.closeDoor()
            d += 1
            s.moveRight()
        return lastOpen - firstOpen

# Definition for a street.
# class Street:
#     def closeDoor(self):
#         pass
#     def isDoorOpen(self):
#         pass
#     def moveRight(self):
#         pass
class Solution:
    def houseCount(self, s: Optional['Street'], k: int) -> int:
        firstOpen = None
        lastOpen = 0
        d = 0
        while d - lastOpen <= k:
            if s.isDoorOpen():
                if not firstOpen:
                    firstOpen = d
                lastOpen = d
                if firstOpen != lastOpen:
                    s.closeDoor()
            d += 1
            s.moveRight()
        return lastOpen - firstOpen

The time complexity is O(K) – assuming the closing door is O(1) constant/trivial.

–EOF (The Ultimate Computing & Technology Blog) —