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.
Reference : http://www.careercup.com/question?id=4863869499473920
Approach:
- Insert all the digits into hast table
- Create a powerset of digits except empty set (Power Set)
- Multiply all the digits in the individual powerset and insert into Hash Table.
- If any point, number already present in the Hash table, return false
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
import java.util.Hashtable; | |
public class ColorfulNumbers { | |
Hashtable<Integer, Integer> ht = new Hashtable<>(); | |
boolean [] used; // for creating powerset, every digit, either | |
//it will be selected or not | |
public int [] getdigits(int Number){ | |
int length = String.valueOf(Number).length(); | |
int A [] = new int [length]; | |
int counter = length–1; //start filling from the end | |
while(Number>0){ | |
int x = Number%10; | |
Number = Number/10; | |
A[counter]=x; | |
counter—; | |
} | |
return A; | |
} | |
public boolean getColorFul(int Number){ | |
ht.clear(); | |
int [] A = getdigits(Number); | |
used = new boolean[A.length]; | |
return powerSet(A, used, 0); | |
} | |
public boolean powerSet(int [] A, boolean [] used, int x){ | |
if(x==used.length–1){ | |
used[x] = false; | |
boolean b = insertInHash(A, used); | |
if(b){ | |
used[x] = true; | |
return insertInHash(A, used); | |
}else{ | |
return false; | |
} | |
} | |
used[x] = false; | |
boolean p = powerSet(A, used, x+1); | |
used[x] = true; | |
return p & powerSet(A, used, x+1); | |
} | |
public boolean insertInHash(int [] A, boolean [] used){ | |
int Sum=0; | |
for(int i = 0;i<used.length;i++){ | |
if(used[i]){ | |
if(Sum==0){ | |
Sum =A[i]; | |
} | |
else{ | |
Sum*=A[i]; | |
} | |
} | |
} | |
if(ht.containsKey(Sum)){ | |
return false; | |
}else{ | |
ht.put(Sum, 1); | |
return true; | |
} | |
} | |
public static void main(String[] args) { | |
ColorfulNumbers c = new ColorfulNumbers(); | |
System.out.println(" 326 Colorful?? " + c.getColorFul(326)); | |
System.out.println(" 3245 Colorful?? " + c.getColorFul(3245)); | |
} | |
} |
Output:
326 Colorful?? false 3245 Colorful?? true