Objective: Algorithm for colorful numbers in c++Given a number, find out whether its colorful or not.
Colorful Number: When in a given number, the product of every digit of a sub-sequence is different. That number is called Colorful Number.
Example:
Given Number : 3245 Output : Colorful Number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245. this number is a colorful number, since product of every digit of a sub-sequence are different. That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20, (3*2*4)= 24 (2*4*5)= 40 Given Number : 326 Output : Not Colorful. 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12.
Reference : CarrerCup & https://algorithms.tutorialhorizon.com/colorful-numbers/
Approach:
- Insert all the digits into hast table
- Create a powerset of digits except for empty set- Power set
- Multiply all the digits in the individual powerset and insert it into the Hash Table.
- If any point, a number already present in the Hash table, return false
Hungry for more algorithms ? Click here.
