Epic Systems Interview Question
Software DevelopersCountry: United States
Interview Type: Written Test
I tried the same approach. But this code finds all possible combinations.
Means for number 1234, combination 123 and combination 321 are treated as different. But product of their digits will be same.
So with this code, I think number can never be colorful.
1) If length of number <= 2 => colorful
2) If all digits are same => not colorful
3) If there are at least two different digits and at least on digit appears more than once => not colorful
4) otherwise we have the following situation. We have set of digits where at least 2 different digits and all digits appear only once or does not appear at all, which means that number of digits in this set < 10. Now lets try all possible combinations (2 ^ 10 with max product < 400000) and save product in set, if we meet some product twice => not colorful, otherwise colorful.
the code below illustrates the idea
char []a = next().toCharArray();
int n = a.length;
if (n <= 2) {
System.out.println("colorful");
return;
}
int []c = new int[10];
for(int i = 0; i < n; ++i) c[a[i] - '0']++;
int size = 0;
boolean hasMoreThanOne = false;
for(int i = 0; i < 10; ++i) {
if (c[i] > 0) ++size;
if (c[i] > 1) hasMoreThanOne = true;
}
if (size == 1) {
System.out.println("not colorful");
return;
}
if (hasMoreThanOne) {
System.out.println("not colorful");
return;
}
int []set = new int[400000];
for(int mask = 0; mask < (1<<n); ++mask) {
if (Integer.bitCount(mask) <= 1) continue;
int prod = 1;
for(int i = 0; i < n; ++i) {
if ((mask & (1 << i)) > 0) {
prod *= (a[i] - '0');
}
}
if (set[prod] > 0) {
System.out.println("not colorful");
return;
}
++set[prod];
}
System.out.println("colorful");
Solution in C++. It's pretty much the same algorithm as posted by the other people.
#include <vector>
#include <string>
#include <iostream>
#include <set>
typedef std::vector<int> IntVector;
typedef std::vector<IntVector> IntVecVector;
IntVecVector powerset(const IntVector &V)
{
IntVecVector S;
int i;
S.push_back(IntVector());
for (i = 0; i < V.size(); ++i) {
IntVecVector s = S;
int j, n = s.size();
for (j = 0; j < n; ++j) {
s[j].push_back(V[i]);
}
S.insert(S.end(), s.begin(), s.end());
}
return S;
}
bool colorful(const IntVecVector &S)
{
std::set<int> mults;
int i;
for (i = 0; i < S.size(); ++i) {
int j, n = S[i].size();
int m = 1;
for (j = 0; j < n; ++j) {
m *= S[i][j];
}
std::pair<std::set<int>::iterator, bool> x = mults.insert(m);
if (x.second == false) return false;
}
return true;
}
int main(int argc, char *argv[])
{
std::string word = argv[1];
int i, n = word.length();
IntVector V;
V.reserve(n);
for (i = 0; i < n; ++i) {
int d = (int)(word[i] - '0');
V.push_back(d);
}
const IntVecVector S = powerset(V);
bool r = colorful(S);
if (r) {
std::cout << "Colorful\n";
}
else {
std::cout << "Not colorful\n";
}
return 0;
}
I think it can be solved without finding permutation or combination
For example 1234, In this example all the digits are prime number and non repeating, and hence it will be a perfect color.
Another example : 6392.
In the above example all numbers are unique but not prime.
So we will try to find the prime factor of all the number , if the prime factors are repeated with any of the existing digits, it means its not perfect color. Like in the above example
3*3
3*2
3,
2 Prime factors are common and hence it cannot be perfect color.
If all the digits are unique, its colorful, other wise its not
public static void colorfull(int num)
{
ArrayList list = new ArrayList();
ArrayList tempList = new ArrayList();
ArrayList multiplication = new ArrayList();
string tempString = num.ToString();
if (tempString.Length < 3)
{
Console.WriteLine("Number is less than three digits");
return;
}
for (int i = 0; i < tempString.Length; i++)
{
list.Add(tempString[i]);
}
foreach (Char x in list)
{
if (!tempList.Contains(x))
{
tempList.Add(x);
}
}
if (tempList.Count == list.Count)
{
Console.WriteLine("Colorfull !!! ");
}
else
{
Console.WriteLine("Not Colorfull !!! ");
}
}
public class Test1 {
static Hashtable <Integer,Integer> h =new Hashtable<Integer,Integer>();
public static int contains(String str)
{
int sum=1;
for(int i=0;i<str.length();i++)
sum*=str.charAt(i)-'0';
return sum;
}
public static boolean number(String num,int start,int rem,String str)
{
if (rem==0&&h.containsKey(contains(str)))
{
System.out.println(contains(str));
System.out.println("here");
return false;
}
else if (rem==0&&h.containsKey(contains(str))==false)
{
h.put(contains(str), 1);
System.out.println(str+" "+contains(str)+" ");
return true;
}
int i=start;
for (;i<num.length();i++)
if (number(num,i+1,rem-1,str+num.charAt(i))==false) break;
if (i!=num.length()) return false;
else return true;
}
public static void main(String[] args) {
String num = String.valueOf(194);
boolean sol = true;
for (int i=2;i<num.length();i++)
if (number(num,0,i,"")==false)
{
sol=false;
break;
}
System.out.println(sol);
}
}
public class Test1 {
static Hashtable <Integer,Integer> h =new Hashtable<Integer,Integer>();
public static int contains(String str)
{
int sum=1;
for(int i=0;i<str.length();i++)
sum*=str.charAt(i)-'0';
return sum;
}
public static boolean number(String num,int start,int rem,String str)
{
if (rem==0&&h.containsKey(contains(str)))
{
System.out.println(contains(str));
System.out.println("here");
return false;
}
else if (rem==0&&h.containsKey(contains(str))==false)
{
h.put(contains(str), 1);
System.out.println(str+" "+contains(str)+" ");
return true;
}
int i=start;
for (;i<num.length();i++)
if (number(num,i+1,rem-1,str+num.charAt(i))==false) break;
if (i!=num.length()) return false;
else return true;
}
public static void main(String[] args) {
String num = String.valueOf(194);
boolean sol = true;
for (int i=2;i<num.length();i++)
if (number(num,0,i,"")==false)
{
sol=false;
break;
}
System.out.println(sol);
}
}
This is a simple java solution. I try to find all subsets greater than size 1 and then calculate the product and if it is unique, return true; else false.
import java.util.ArrayList;
public class ColorfulNumber {
public static boolean checkColorful(int num) {
String str = String.valueOf(num);
ArrayList<Integer> array = new ArrayList<Integer>();
for(int i=0; i<str.length(); i++) {
int a = str.charAt(i);
a = a - 48;
array.add(a);
}
ArrayList<Integer> products = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> subsets = getSubsets(array);
for(ArrayList<Integer> set : subsets) {
if(set.size() >= 2) {
int val = 1;
for(int i=0; i<set.size(); i++) {
val = val * set.get(i);
}
if(!products.contains(val)) {
products.add(val);
}
else {
return false;
}
}
}
return true;
}
public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> array) {
ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
if(array.size() == 0) {
subsets.add(new ArrayList<Integer>());
}
else {
ArrayList<Integer> array_copy = new ArrayList<Integer>();
array_copy.addAll(array);
int first = array_copy.remove(0);
ArrayList<ArrayList<Integer>> reduced_set = getSubsets(array_copy);
subsets.addAll(reduced_set);
reduced_set = getSubsets(array_copy);
for(ArrayList<Integer> set : reduced_set) {
set.add(0, first);
}
subsets.addAll(reduced_set);
}
return subsets;
}
public static void main(String args[]) {
System.out.println(checkColorful(235));
}
}
my simple naive sol
bool isColorful(int num){
num=abs(num);
unordered_set<int> checker{};
while(num!=0){
int n{num%10};
if(n==0||n==1) return false;
if(!checker.insert(num%10).second) return false;
num/=10;
}
vector<vector<int>> vec{};
unordered_set<int> checker_2(checker);
auto pos=find_if(checker.cbegin(),checker.cend(),[&](int num){
bool res{false};
size_t sz = vec.size();
for(int i=0;i!=sz;i++){
vec.push_back(vec[i]);
vec[i].push_back(num);
int total= accumulate(vec[i].begin(),vec[i].end(),1,[&](int x,int y){return x*y;});
res=!checker_2.insert(total).second;
}
vec.push_back({num});
return res;
});
if(pos!=checker.end()) return false;
return true;
}
boolean isNoColorful(int n){
int numberOfDigits = 0;
int tempNumber = n;
//First get the number of digits
while(tempNumber>0){
tempNumber/=10;
numberOfDigits++;
}
//Make an array of digits
int digits[]=new int[numberOfDigits];
tempNumber=n;
int i=0;
while(tempNumber>0){
digits[i]=tempNumber%10;
tempNumber/=10;
i++;
}
/*Now use bitwise increment to get the combinations of digits.
Eg: If no of digits are 3, increment a counter from 0 to 8 which is nothing but
000,001,010,011,100,101,110,111
Multiply the digits for which the index is set and check if it is unique by using a HashSet.
And voila, you have solved the problem.
*/
int counter=0;
int product=0;
HashSet<Integer> listOfProducts = new HashSet<Integer>();
int powerSetCount = pow(2,numberOfDigits);
for(j=0;j<powerSetCount;j++){
counter++;
for(k=0;k<numberOfDigits;k++){
if(counter&(1<<k)){
product=product*digits[k];
}
}
if(!listOfProducts.contains(product)){
listOfProducts.add(product);
} else {
return false;
}
}
return true;
}
boolean isNoColorful(int n){
int numberOfDigits = 0;
int tempNumber = n;
while(tempNumber>0){
tempNumber/=10;
numberOfDigits++;
}
int digits[]=new int[numberOfDigits];
tempNumber=n;
int i=0;
while(tempNumber>0){
digits[i]=tempNumber%10;
tempNumber/=10;
i++;
}
int counter=0;
int product=0;
HashSet<Integer> listOfProducts = new HashSet<Integer>();
int powerSetCount = pow(2,numberOfDigits);
for(j=0;j<powerSetCount;j++){
counter++;
for(k=0;k<numberOfDigits;k++){
if(counter&(1<<k)){
product=product*digits[k];
}
}
if(!listOfProducts.contains(product)){
listOfProducts.add(product);
} else {
return false;
}
}
return true;
}
It'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
I'm not sure there's a more efficient way, because we have to consider all valid combinations.
- acannon828 February 12, 2015