0
\$\begingroup\$

Given an input color string in the format "#ABCDEF", representing a red-green-blue color, find the shorthand representation of that color that is most similar to the given color. Shorthand representation is in the form "#XYZ", where X, Y, and Z are one of the 16 possible hexadecimal values \$(0-9, A-F)\$.

The similarity between two colors "#ABCDEF" and "#UVWXYZ" is calculated as \$-(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2\$.

Example 1: Input: color = "#09f166" Output: "#11ee66" Explanation: The similarity is calculated as \$-(0x09 - 0x11)^2 - (0xf1 - 0xee)^2 - (0x66 - 0x66)^2\$ = -64 - 9 - 0 = -73. The shorthand color "#11ee66" has the highest similarity.

Example 2: Input: color = "#4e3fe1" Output: "#5544dd"

Constraints:

The input color has a length of 7 characters. The first character of color is '#'. The remaining characters of color are either digits or lowercase characters in the range ['a', 'f'].

Question: I am asked to return the shorthand representation of the color that has the highest similarity to the given color.

Approach 1: wrong solution as it seems where I tried to loop over all possible values r=r+1, g=g+1, b=b+1 in 3 for loops and then find the similarity after combing rgb in one color and finding similarity with input color.

public class Solution {
    public String similarRGB(String color) {
        // Convert the given color to its RGB representation
        int[] rgb = new int[3];
        for (int i = 1; i <= 5; i += 2) {
            rgb[(i - 1) / 2] = Integer.parseInt(color.substring(i, i + 2), 16);
        }

        // Initialize variables to keep track of the highest similarity and the best shorthand color
        int maxSimilarity = Integer.MIN_VALUE;
        String bestShorthand = "";

        // Iterate through all possible shorthand colors
        for (int r = 0; r <= 255; r += 1) {
            for (int g = 0; g <= 255; g += 1) {
                for (int b = 0; b <= 255; b += 1) {
                    // Calculate the similarity with the given color
                    int similarity = -(squareDiff(r, rgb[0]) + 
                                       squareDiff(g, rgb[1]) +
                                       squareDiff(b, rgb[2]));

                    // Update the best shorthand color if the current similarity is higher
                    if (similarity > maxSimilarity) {
                        maxSimilarity = similarity;
                        bestShorthand = "#" + toHex(r) + toHex(g) + toHex(b);
                    }
                }
            }
        }

        return bestShorthand;
    }

    // Helper method to calculate the squared difference between two numbers
    private int squareDiff(int a, int b) {
        return (a - b) * (a - b);
    }

    // Helper method to convert a decimal number to its two-digit hexadecimal representation
    private String toHex(int num) {
        String hex = Integer.toHexString(num);
        return hex.length() == 1 ? "0" + hex : hex;
    }
}

Approach 2: correct solution as it seems. We have to loop in a step of 17 r=r+17, g=g+17, b=b+17 in 3 for loops and then find the similarity after combing rgb in one color and finding similarity with input color. This seems to be the correct solution. We keep the code above as its but we just change the increment of the inner 3 for loops:

// Iterate through all possible shorthand colors
for (int r = 0; r <= 255; r += 17) {
    for (int g = 0; g <= 255; g += 17) {
        for (int b = 0; b <= 255; b += 17) {
            // Calculate the similarity with the given color
            int similarity = -(squareDiff(r, rgb[0]) + 
                               squareDiff(g, rgb[1]) +
                               squareDiff(b, rgb[2]));

            // Update the best shorthand color if the current similarity is higher
            if (similarity > maxSimilarity) {
                maxSimilarity = similarity;
                bestShorthand = "#" + toHex(r) + toHex(g) + toHex(b);
            }
        }
    }
}

I am not sure why my approach is wrong and approach 2 is right?

\$\endgroup\$
5
  • 2
    \$\begingroup\$ How can you tell whether a solution is right or wrong? Is there a reference answer? \$\endgroup\$
    – Reinderien
    Commented Jul 29, 2023 at 23:47
  • \$\begingroup\$ LeetCode test cases. So this is already solved and discussed there, but I don't get why the approach 1 is not right while the second is right \$\endgroup\$
    – Avv
    Commented Jul 30, 2023 at 0:15
  • 1
    \$\begingroup\$ CodeReview is not a good fit for this question. You need to know why your code works the way it does, and non-working code is off topic. \$\endgroup\$
    – Reinderien
    Commented Jul 30, 2023 at 0:30
  • \$\begingroup\$ SO asked me to post it here! \$\endgroup\$
    – Avv
    Commented Jul 30, 2023 at 2:00
  • 2
    \$\begingroup\$ People on SO often don’t know what this site is about. Take their recommendations with a grain of salt. Always look at the site’s help center, especially the “what topics can I ask about here?” section: codereview.stackexchange.com/help/on-topic \$\endgroup\$ Commented Jul 30, 2023 at 3:30

1 Answer 1

1
\$\begingroup\$

Not having run it, Approach 1 looks like it would just be the identity function, spitting out exactly what went in. That is, there's no rounding.

An input like #ABCDEF should be rounded off to #BBDDFF. A smaller value like #234567 would round in the other direction to #224466, and color values in the neighborhood of 0x80 might go up or down depending on what the other two colors are doing.

Approach 2 produces correct results but it seems expensive, going through 2 ** 12 loops. After quantizing to multiples of 0x11 (multiples of 17), surely we only need to go up or down a single value, right? So testing eight candidates, instead of four thousand, should suffice.

\$\endgroup\$
7
  • \$\begingroup\$ Thank you very much. Yeah this questions seems off like it's using shorthand pairs of same value like "00", "11", "22", "33", "44", "55", "66", "77", "88", "99", "aa", "bb", "cc", "dd", "ee", "ff", but I don't get it? Why we can't just loop through all possible combinations, why would that yield a wrong answer? \$\endgroup\$
    – Avv
    Commented Jul 30, 2023 at 15:56
  • 1
    \$\begingroup\$ Why? Because between e.g. 11 and 22 the 1st approach contemplates return values such as 12, 13, 14 ... . But those aren't valid return values. Only a value congruent to zero mod 17 can be valid, according to the rules of shorthand abbreviation. That is, the shorthand cannot express a value such as 12, it simply isn't a thing, it would get truncated back down to 11. It's like asking someone "give me an integer value -- it must be between 3 and 4 non-inclusive". It simply isn't a thing. \$\endgroup\$
    – J_H
    Commented Jul 30, 2023 at 16:46
  • \$\begingroup\$ Thank you. But hexadecimal numbers go all the way from 01 to 0F, so we have 16 colors for each number from [0, F], so total we have 16x16 for each pair in the color that has 3 pairs of hexadecimal numbers after the hash sign #. I still don't get it why we choose specific shorthands numbers "00", "11", "22", "33", "44", "55", "66", "77", "88", "99", "aa", "bb", "cc", "dd", "ee", "ff". Can you please explain or add more math if possible to explain what you mean? \$\endgroup\$
    – Avv
    Commented Jul 30, 2023 at 20:41
  • 1
    \$\begingroup\$ Let's talk about the half-open unit interval [0, 1). It includes values from 0.0 up to 0.9999... Now let's discretize to 256 levels. Black is 0x00. The whitest we can get is 0xFF, which is almost 0x100 but not quite, reminding us of that repeating 9. That is, 255/256ths is almost 1.0 but it falls slightly short, due to quantizing. Shorthand notation multiplies by 17 instead of 16 because we wish full range, for 000 to be black and fff to be very bright white: ffffff rather than f0f0f0. \$\endgroup\$
    – J_H
    Commented Jul 30, 2023 at 21:22
  • 1
    \$\begingroup\$ Well, there's two different things going on here, right? (1) The historic shorthand usage that sprang up before 2000, #789 vs #778899, and then (2) the phrasing of a problem which takes advantage of that shorthand. Now maybe the phrasing could have been better. But the shorthand is what it is, and it's widely used. Its motivation is rooted in the desire to cover as much of that [0, 1) unit interval as possible. \$\endgroup\$
    – J_H
    Commented Jul 31, 2023 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.