800. Similar RGB Color
Model: qwen2.5-coder:14b
Topics: Math,String
FAANG asked: 1
Acceptance rate: 62.5%
Problem Breakdown
The problem asks us to find the shorthand color (a 7-character hexadecimal string) that is most similar to a given RGB color in its expanded form. The similarity between two colors is calculated using the formula -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2, where #ABCDEF and #UVWXYZ are the expanded forms of the shorthand colors.
Inputs:
- A string
colorrepresenting an RGB color in the format"#ABCDEF".
Outputs:
- A string representing the most similar shorthand color in the format
"#XYZ".
Implicit Constraints or Tricky Edge Cases:
- The input is always a valid 7-character hexadecimal string.
- The output must be in lowercase letters.
- The similarity calculation involves squaring differences, so negative values are not applicable here.
Intuition
The brute-force approach would involve checking all possible shorthand colors (#000 to #fff) and calculating their similarity to the given color. This approach is inefficient because it requires 4096 iterations (16^3), which is computationally expensive.
A better approach involves understanding that each pair of hexadecimal digits in the expanded form can be rounded to the nearest shorthand digit. For example, 0x09 rounds to 0x11, and 0xf1 rounds to 0xee. This insight reduces the problem to a simple rounding operation for each color component.
Approach
-
Extract Each Color Component:
- Extract the red, green, and blue components from the input string.
-
Round Each Component:
- Convert each component from hexadecimal to decimal.
- Round the decimal value to the nearest multiple of 17 (since
0x11,0x22, …,0xffare the possible shorthand values). - Convert the rounded decimal value back to a two-character hexadecimal string.
-
Construct the Result:
- Concatenate the rounded components with the
#prefix to form the final shorthand color.
- Concatenate the rounded components with the
Complexity Analysis
- Time Complexity: O(1) because we always perform a fixed number of operations (extracting and rounding three components).
- Space Complexity: O(1) because we use a constant amount of extra space for storing intermediate results.
Solution
def similarRGB(color: str) -> str:
def round_to_nearest_shorthand(hex_val):
# Convert hex to decimal
dec_val = int(hex_val, 16)
# Round to nearest multiple of 17 (0x11, 0x22, ..., 0xff)
rounded_dec = round(dec_val / 17) * 17
# Convert back to hex and pad with zero if necessary
return format(rounded_dec, '02x')
# Extract each color component
red = color[1:3]
green = color[3:5]
blue = color[5:7]
# Round each component and construct the result
rounded_red = round_to_nearest_shorthand(red)
rounded_green = round_to_nearest_shorthand(green)
rounded_blue = round_to_nearest_shorthand(blue)
return f"#{rounded_red}{rounded_green}{rounded_blue}"
Edge Cases Handled
- Exact Matches: If the input color is already a shorthand (e.g.,
#11ee66), the function will correctly return it as is. - Minimum and Maximum Values: The function handles colors with minimum (
#000000) and maximum (#ffffff) values correctly by rounding to the nearest valid shorthand value.