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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Similar RGB Color

Number: 818

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

Given a standard 6-digit hex color string (e.g., "#ABCDEF"), find the shorthand color (i.e., one that can be represented as "#XYZ" where each two-digit component is X repeated) that is most similar to the given color. The similarity between two colors is computed as the negative sum of squared differences between their corresponding R, G, and B components.

Key Insights

  • Each two-digit component (e.g., "AB") represents a value between 0 and 255.
  • A shorthand component is derived by repeating a single hex digit (e.g., "X" becomes "XX", which is equivalent to X*17).
  • For each component (red, green, blue), the goal is to find the hex digit X (0 to 15) such that 17*X is as close as possible to the original component's integer value.
  • Rounding the original value divided by 17 (with proper adjustment) gives the best possible shorthand component.
  • The problem requires processing exactly three components, leading to a constant time solution.

Space and Time Complexity

Time Complexity: O(1) – Only three components are computed. Space Complexity: O(1) – Uses a constant amount of extra space.

Solution

The solution involves processing each of the three two-character substrings corresponding to red, green, and blue components.

  1. Convert each two-character substring from hexadecimal to an integer.
  2. For each integer value, find the closest multiple of 17. Since a repeated hex digit represents a number equal to 17 times the digit (e.g., digit 0xA repeated gives 0xAA == 17*A), you can obtain the best candidate by rounding (v + 8)/17.
  3. Convert the rounded digit back into a hexadecimal string and construct its two-character representation by repeating the hex digit.
  4. Concatenate these results prefixed with '#' to return the most similar shorthand color.

This approach leverages simple arithmetic and string manipulation, ensuring a straightforward solution that is easy to reason about and implement.

Code Solutions

# Python solution with detailed line-by-line comments
class Solution:
    def similarRGB(self, color: str) -> str:
        # Function to find the closest shorthand string for a given 2-digit hex color component.
        def get_closest(component: str) -> str:
            # Convert the 2-digit hex component to an integer.
            value = int(component, 16)
            # Find the nearest integer in the range 0-15 that when multiplied by 17 will be most similar to 'value'.
            # Adding 8 effectively rounds the division.
            digit = (value + 8) // 17
            # Format the digit back into a hex string (without '0x' prefix) and repeat the character.
            return format(digit, 'x') * 2

        # Construct the final color by processing each of the three components (red, green, blue).
        return "#" + get_closest(color[1:3]) + get_closest(color[3:5]) + get_closest(color[5:7])

# Example usage:
# solution = Solution()
# print(solution.similarRGB("#09f166"))
← Back to All Questions