Skip to content

Instantly share code, notes, and snippets.

@Eatkin
Created April 19, 2023 08:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Eatkin/356a438ad9607d4e3a944a9f4475d23e to your computer and use it in GitHub Desktop.
Save Eatkin/356a438ad9607d4e3a944a9f4475d23e to your computer and use it in GitHub Desktop.
Algorithm to return if a number is colorful
'''A number is colorful if all products of the subsets of individual digits are unique
e.g. 263 is colorful:
2 * 6 * 3 = 36
2 * 6 = 12
6 * 3 = 18
'''
def is_colorful(num):
# Account for negatives (results will be the same)
num = abs(num)
# Number is trivially colorful if only contains 1 digit
if num < 10:
return True
# This is the maximum possible colorful number, contains no repeated digits, no 1s or 0s
# (although it is not colourful)
if num > 98765432:
return False
num_list = [int(digit) for digit in str(num)]
cache = set(num_list)
'''Trivial cases:
Number contains a 0 - 0x = 0
Number contains a 1 - 1x = x
Length of number is larger than cache - digits are repeats'''
length = len(num_list)
if 0 in num_list or 1 in num_list or length > len(cache):
return False
# Finally calculate the products after filtering trivial cases
for i in range(length - 1):
product = num_list[i]
for j in range(i + 1, length):
product *= num_list[j]
if product in cache:
return False
cache.add(product)
return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment