This post is completed by 2 users
|
Add to List |
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:
- Initialize a Set
- Get the length of number (number of digits)
- User Two nested loops,
- 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.
- 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
Code:
Output:
326 Colorful?? false 3245 Colorful?? true
Reference : http://www.careercup.com/question?id=4863869499473920
Also Read: