Similar RGB Color

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes

Problem statement

The similarity between two RGB color codes say "#ABCDEF" and "#UVWXYZ" is defined as negative of (hex(AB) - hex(UV)) ^ 2 + (hex(CD) - hex(WX)) ^ 2 + (hex(EF) - hex(YZ)) ^ 2. Where hex() is the hexadecimal value corresponding to the input character.

An RGB color code is called perfect if it is in form of ‘#AABBCC’. For example, ‘#11aabb’, ‘#000011’, and ‘#aabbff’ are perfect RGB color codes but ‘#123456’, ‘#112234’ are not perfect.

Note: 
An RGB color code is consists of 7 characters in which the first character is ‘#’ and every other character represents a hexadecimal digit from 0 to f.

You are given a string of size 7 that represents an RGB color code, Your task is to find a perfect RGB color code that is most similar to the given RGB color code, i.e. have the maximum similarity value.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a string ‘color’ representing an RGB color code.
Output Format: 
For each test case, print a string that represents a perfect RGB color code and is most similar to the given RGB color code.

The output of each test case will be printed in a separate line.
Note: 
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
length of color = 7 
color[0] = ‘#’
Color[i] is a hexadecimal digit from 0 to f, for every i - 1 to 6.

Time Limit: 1sec
Sample Input 1:
2
#01aa45
#000000
Sample Output 1:
#00aa44
#000000
Explanation For Sample Input 1:
Test case 1:

‘#00aa44’ is the perfect rgb color code that is most similar to the the given string as -( ((01) - (00)) ^ 2 + ((aa) - (aa)) ^ 2 + ((45) - (44)) ^ 2) = - (1 + 0 + 1) = -2 which is the maximum possible. 

Test case 2:

The given string is already a perfect RGB color code, so we can return the same.
Sample Input 2:
1
#fa4411
Sample Output 2:
#ff4411
Hint

There are not many cases, try to think of solution by considering all cases

Approaches (1)
Brute Force Approach

We know that the given string can be divided into three parts, and each part can be handled separately. 

 

For example, for the string "#09f166", we will process "09", ''f1”, and ''66”separately. Our goal is to make the two characters of each part the same with the smallest distance from the original. In fact, there are not many choices for each path as there can be only 16 characters possible i.e [ ‘0’, ‘1’, ‘2’ …. ‘f’ ].

 

Algorithm:

 

  • Let the given string be ‘color’.
  • Declare an array, say ‘hexValue’ that contains a value of 16 hexadecimal substrings from ‘00’ to ‘ff’, i.e [ hex(00), hex(11), hex(22) … hex(FF) ].
  • Declare a string that says ‘answer’ that will store the resultant string.
  • Run a loop from i = 0 to 2 to iterate over each part of the string.
    • Declare a string say ‘curr’ to store the substring of length 2 from ‘color’, i.e. ‘curr’ = ‘color [2*i +1 to 2*i + 2]’
    • Convert string ‘curr’ into decimal value that corresponds to a hexadecimal value of ‘curr’ and store it in a variable say ‘val’.
    • Find the index ‘j’ in ‘hexValue’ such that abs ( ‘hexValue [j]’ - ‘val’ ) is minimum.
    • Add hexadecimal value corresponding to ‘ hexValue[j]’ in ‘answer’.
  • Convert ‘answer’ into the string format.
  • Return ‘#’ + ‘answer’.
Time Complexity

O(1)

 

As there are only at most 16 possible hexadecimal, and we are iterating over these only 3 times that takes constant time. Hence the overall time complexity is O(1).

Space Complexity

O(1)

 

We are using an array to store values corresponding to hexadecimal values of 16 elements that will take constant space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Similar RGB Color
Full screen
Console