acannon828
BAN USERIt's a little confusing what is meant by permutations in this sense. Normally permutations refers to any re-ordering of an entire set, so permutations for 1234 would be 1243, 1423, 1432, etc.
Combinations, on the other hand, refer to selections from a set where order is disregarded. This is more along the lines of what the question seems to refer to, but all combinations would include subsets of just a single digit, which it seems we are excluding.
1. Compute all combinations (of size > 1) of the number's digits
2. For each combination, compute the product of the digits it contains.
3. Hash that product to a hash table, on a collision with a hash table item with the same product return false.
4. Return true if/when the for loop completes
def getCombinationsOfSizeGreaterThanOne(aNumber):
if len(aNumber) == 2:
return [[aNumber[0], aNumber[1]]
currentCombos = getCombinationsOfSizeGreaterThanOne(aNumber[1:])
newCombos = []
for combo in currentCombos:
newCombos.append(aNumber[0] + currentCombo)
return newCombos + currentCombos
def isColorful(aNumber):
combos = getCombinationsOfSizeGreaterThanOne(aNumber)
comboProducts = {}
for combo in combos:
product = 1
for digit in combo:
product *= digit
if comboProducts.contains(product):
return False
return True
I'm not sure there's a more efficient way, because we have to consider all valid combinations.
- acannon828 February 12, 2015
@techpanja You need to remove elements from your hashmap after a duplicate is found.
- acannon828 February 23, 2015