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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Houses at a Certain Distance I

Number: 3271

Difficulty: Medium

Paid? No

Companies: Oracle

Problem Description

Given n houses labeled from 1 to n arranged in a straight line (with each consecutive pair connected by a street) along with an extra street connecting house x and house y (which can be the same), determine for each distance k from 1 to n the total number of ordered pairs of houses (house1, house2) such that the minimum number of streets needed to travel between them is exactly k.

Key Insights

  • The basic distance between any two houses i and j (with i < j) is simply j - i.
  • The extra edge from x to y may offer a shorter route; for any pair (i, j), compute two alternate distances: one by going from i to x, using the extra edge to y, then going to j, and another by going from i to y, using the extra edge to x, then going to j.
  • Due to symmetry, each pair (i, j) where i < j contributes two ordered pairs: (i, j) and (j, i).

Space and Time Complexity

Time Complexity: O(n^2) – We loop for each pair (i, j) among n houses. Space Complexity: O(n) – We store an array of size n to count the number of pairs for each distance.

Solution

We iterate over every unordered pair of distinct houses (i, j) with i < j. For each pair, we calculate three possible distances:

  1. The direct path along the line: j - i.
  2. A path that goes from i to x, uses the extra street (cost 1), and then goes from y to j.
  3. A path that goes from i to y, uses the extra street (cost 1), and then goes from x to j. We take the minimum of these three as the actual distance between i and j. Since the pair counts are for ordered pairs, we add 2 for each pair with that minimum distance. The algorithm leverages a simple brute-force enumeration, which is efficient given n is at most 100.

Code Solutions

# Python solution for Count the Number of Houses at a Certain Distance I

def count_houses(n, x, y):
    # Initialize result array with zeros; index 0 unused for 1-indexing
    result = [0] * (n + 1)
    
    # Iterate over each unordered pair (i, j) with i < j
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            # Direct distance as the baseline
            direct = j - i
            # Distance using the extra edge from x to y
            via_extra1 = abs(i - x) + 1 + abs(j - y)
            via_extra2 = abs(i - y) + 1 + abs(j - x)
            # Compute the minimum distance among the three possibilities
            min_distance = min(direct, via_extra1, via_extra2)
            # Each unordered pair gives two ordered pairs.
            result[min_distance] += 2
            
    # Return the result array for distances from 1 to n (1-indexed)
    return result[1:]

# Example usage:
print(count_houses(3, 1, 3))  # Expected output: [6,0,0]
print(count_houses(5, 2, 4))  # Expected output: [10,8,2,0,0]
print(count_houses(4, 1, 1))  # Expected output: [6,4,2,0]
← Back to All Questions