This post is completed by 7 users

  • 3
Add to List
Hard

123. Colorful Numbers

Objective: Given a number, find out whether its colorful or not.

Colorful Number: When in a given number, product of every digit of a sub-sequence are different. That number is called Colorful Number. See Example

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.

Approach:

Idea is to get the product of all possible subarrays and keep storing it in a Set, if any time current subarray product is already in Set, return false, else at the end return true 

Read - Print all subarrays of a given array Video - https://www.youtube.com/watch?v=xHwMaxq2Qxo

Steps:

  1. Initialize a Set
  2. Get the length of number (number of digits)
  3. User Two nested loops, 
  4. first loop sets the starting point of subarray and second loop will decide the length of the subarray. This will give one of the possible subarray, get the product and check if product already exists it in Set. If yes, then return false, number is not colorful.
  5. If done with iterations, and all products are added to Set, that means no two subarray has same product, return true since number is colorful

Output:

326 Colorful?? false
3245 Colorful?? true

Reference : http://www.careercup.com/question?id=4863869499473920