Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
We can check for the presence of 0 or 1 in the colorString and return false if they are present. Eg: 206 or 216 are not colorful numbers
I think without adding the condition for 0 or 1, the above code will produce correct output
There are a few things that would preclude a number being a colorful number:
1. Having duplicate digits and more than 2 digits (if the number were '22', that would okay since 2*2 = 4 but 223 would not be okay since it would have two 2 * 3 computations)
2. the products of all subsets with |n| > 1 must not be duplicated or equal to another digit
3. (implied) 1 and 0 cannot be in the number since due to their properties
4. (implied) since the number is limited to 8 unique digits, full enumeration of all subsequences is teniable (~O(2^8) max subsequences)
5. (implied) all numbers with 2 digits are acceptable as long as they don't contain '0' or '1'
Approach taken is dynamic where:
Acceptable (n) = for all p in prod(n-1), n * p not in prod(n-1)
prod(n) = prod(n-1) + {for all p in prod(n-1), n * p} + n
prod(0) = {}
Runtime is O(n^2) where n is the number of digits in the number.
public static boolean isColorful(int number){
if(number < 0){
return IllegalArgumentException();
}
//break the number into it's digits
int[] digits = computeDigits(number);
//if the number is less than 3 digits, simply check that they are not 1 or 0
if(digits.length == 0){
return false;
}
if(digits.length == 1){
return digits[0] != 0 && digits[0] != 1;
}
if(digits.length == 2){
return digits[0] != 0 && digits[0] != 1 && digits[1] != 0 && digits[1] != 1;
}
//cache of all previously computed products
HashSet<Integer> cache = new HashSet<Integer>();
for(int i = 0; i < digits.length; i++){
int digit = digits[i];
// cannot be 0 or 1
if(digit == 0 || digit == 1){
return false;
//not duplicates
if(cache.contains(digit)){
return false;
}
//check all products with previous contents
ArrayList<Integer> newProducts = new ArrayList<Integer>(cache.size());
for(Integer oldProd : cache){
Integer newProd = oldProd * digit;
if(cache.contains(newProd)){
return false;
}
newProducts.add(newProd);
}
cache.addAll(newProducts);
cache.add(digit);
}
return true;
}
private static int[] computeDigits(int number){
ArrayList<Integer> digitsList = new ArrayList<Integer>();
while(number > 0){
digitsList.add(number % 10);
number /= 10;
}
int[] results = new int[digitsList.size()];
for(int i = 0; i < results.length; i++){
results[i] = digitsList.get(i);
}
return results;
}
'''
Colorful Number:
A number can be broken into different sub-sequence parts. Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245. And 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
But 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12.
You have to write a function that tells if the given number is a colorful number or not.
'''
def colorful(number):
number_as_list = number_to_int_list(number)
products = []
for i in range(1, len(number_as_list) + 1):
# need to take i at a time
for j in range(0, len(number_as_list)):
if j+i > len(number_as_list):
break
sub_list = number_as_list[j:j+i]
product = reduce(lambda x, y: x * y, sub_list)
if product in products:
return False
products.append(product)
return True
def number_to_int_list(number):
number_as_list = []
while (number > 0):
digit = number % 10
number /= 10
number_as_list = [digit] + number_as_list
return number_as_list
# usage
print (colorful(3245))
print (colorful(326))
print (colorful(22))
print (colorful(1245))
Use state DP for not calculating products, which have already been calculated.
bool getProductResult(int n)
{
char str[100];
sprintf(str,"%d",n);
string s(str);
set<int> products;
set<int>::iterator it;
bool result=true;
int len=s.size();
if (len<=1) return true;
int dp[1<<len];
for(int i=0;i<len;++i)
{
dp[1<<i]=s[i]-'0';
it=products.find(s[i]-'0');
if (it!=products.end())
result=false;
else
products.insert(s[i]-'0');
}
for(int l=2;l<=len && result;++l)
{
int end=len-l;
for(int i=0;i<=end && result;++i)
{
int state=0;
for(int j=i+1;j<i+l;++j)
state|=1<<(len-j-1);
int singleState=1<<(len-i-1);
int completeState=state|singleState;
dp[completeState]=dp[singleState]*dp[state];
it=products.find(dp[completeState]);
if (it!=products.end())
result=false;
else
products.insert(dp[completeState]);
}
}
return result;
}
Pseudocode:
1. Break the given number into indivdual digits.
2. Store these digits into an array.
3. Now , calculate the product of all the possible subsequences and store the result in a set.
4. Repeat step 3 unless there is a duplicate element. In that case , return false.
5. If step 3 never returns false return true.
Here is the implementation :
public class ColorfulNumber {
public static void main(String[] args) {
System.out.println(isColorful(3245));
System.out.println(isColorful(326));
}
static boolean isColorful(int number){
Set<Integer> s = new HashSet<>();
String num = number+"";
int[] digits = new int[num.length()];
for(int i=0;i<num.length();i++){
digits[i]=Integer.parseInt(num.charAt(i)+"");
s.add(digits[i]);
}
for(int i=2;i<num.length();i++){
for(int j=0;j<digits.length-i+1;j++){
int tempi=i;
int tempj=j;
int product=1;
while(tempi>0){
product*=digits[tempj++];
tempi--;
}
if(s.add(product)==false){
return false;
}
}
}
return true;
}
}
#include <algorithm>
#include <set>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
bool isColorful (int myNum){
if (myNum/10 == 0){
return true;
}
unordered_map<int, int> myVector;
int numLength = (int)(log10(myNum)+1);
for (int i = 1; i < numLength; ++i){
int newNum = myNum;
int newNumLength = (int)(log10(newNum)+1);
for (int j = newNumLength+1-i; j >= 1; --j){
int numPush = newNum%((int)pow(10,i));
if ((int)(log10(numPush)+1) > 1){
int x = numPush%10;
int nL = (int)(log10(numPush)+1);
for (int k =1; k <nL; ++k){
if (x == 1 || x == 0){
return false;
}
numPush = numPush/10;
x = x*(numPush%10);
}
numPush = x;
}
if (numPush == 0 || numPush == 1){
return false;
}
myVector[numPush] = 1;
newNum = newNum/10;
}
}
int mySize = 0;
for (int i = 2; i <= numLength; ++i){
mySize = mySize + i;
}
if (mySize > myVector.size()){
return false;
}
return true;
}
int main(){
cout << "Please enter a number: " << endl;
int myNum;
cin >> myNum;
if (isColorful(myNum) == true){
cout << "\nNumber is colorful." << endl;
} else {
cout <<"\nNumber is not colorful." << endl;
}
return 0;
}
// here is simple solution to above problem
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class colourfull_no {
public static void main(String args[])
{
System.out.println(color_test("3245"));
System.out.println(color_test("326"));
System.out.println(color_test("322"));
}
static boolean color_test(String num){
String number=num+"";
ArrayList st1 = new ArrayList();
for(int i=0;i<number.length();i++)
{
for(int j=i+1;j<=number.length();j++)
{
String str1=new String();
str1=number.substring(i,j);
int k,a=0, prod=1;
k=Integer.parseInt(str1);
while(k!=0)
{
a=k%10;
k=k/10;
prod=prod*a;
}
st1.add(prod);
}
}
System.out.println(st1);
Set<Integer> set = new HashSet<Integer>(st1);
if(set.size() < st1.size())
{
return false;
}
else{return true;}
}
}
import java.util.ArrayList;
import java.util.HashSet;
public class ColorfulNumber {
private static boolean isColorfulNumber(int number){
int lengthOfNumber = String.valueOf(number).length();
int numbers[] = new int[lengthOfNumber];
int newNumber = number;
for(int i = 0; i < lengthOfNumber; i++){
numbers[i] = (int) (newNumber / Math.pow(10,lengthOfNumber - i - 1)) ;
newNumber = (int) (newNumber % Math.pow(10,lengthOfNumber - i - 1)) ;
}
ArrayList<Integer> products = new ArrayList<Integer>();
for(int i = 0; i < lengthOfNumber; i++){
int product = numbers[i];
products.add(product);
for(int j = i + 1; j <= lengthOfNumber - 1; j++ ){
product = product * numbers[j];
products.add(product);
}
}
HashSet<Integer> productSet = new HashSet<Integer>(products);
if(products.size() == productSet.size()){
return true;
}
return false;
}
public static void main(String[] args) {
boolean isColorful = isColorfulNumber(3245);
System.out.println(isColorful);
}
}
package ProblemSolving;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.Exception;
import java.lang.Integer;
import java.lang.String;
import java.lang.System;
import java.util.HashSet;
import java.util.Set;
/**
* Colorful Number:
* A number can be broken into different sub-sequence parts.
* Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245.
* And 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
* But 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12.
*/
public class ColorfulNumber {
public static void main(String[] args) throws Exception {
String numString = new BufferedReader(new InputStreamReader(System.in)).readLine();
int num = Integer.parseInt(numString);
int length = numString.length();
int[] digits = new int[length];
int index = length - 1;
Set<Integer> productSet = new HashSet<Integer>();
while (num > 0) {
digits[index] = num % 10;
if(productSet.contains(digits[index]))
{
System.out.println("Not a colorful number");
return;
}else{
//System.out.println("Added "+digits[index]+" at "+index);
productSet.add(digits[index]);
}
num = num / 10;
index--;
}
for (int x = 1; x < length; x++) {
int product = 1;
for(int i=0;i<x;i++)
{
product = product*digits[i];
}
for (int y = x; y < length; y++) {
if(productSet.contains( product * digits[y]))
{
System.out.println("Not a colorful number");
//System.out.println("Not a colorful number "+ product * digits[y]+" exists");
return;
}else{
//System.out.println("Added "+ product * digits[y]);
productSet.add( product * digits[y]);
}
}
}
System.out.println("Colorful number");
}
}
No 1, no 0, no duplicates allowed. For fast prod[i->j] calculation, do prod[0->n] / prod[0->i-1] / reverseprod[j+1 -> n]. O(n^2), O(n).
bool isColorful(int num) {
if (num == 0 || num == 1) return true;
if (num < 0) return false;
// num to vector
vector<int> seq;
vector<bool> check(8, false);
// no 0, no 1, no duplicate
while (num) {
if (num % 10 == 0 || num % 10 == 1 || check[num % 10 - 2]) return false;
check[num % 10 - 2] = true;
seq.push_back(num % 10);
num /= 10;
}
int low(0), high(seq.size() - 1);
while (low < high) swap(seq[low++], seq[high--]);
// calc sequential prod and rev prod.
vector<int> seqprod(seq.size());
seqprod[0] = seq[0];
for (int i = 1; i < seq.size(); ++i) seqprod[i] = seqprod[i - 1] * seq[i];
vector<int> revprod(seq.size());
revprod[seq.size() - 1] = seq.back();
for (int i = seq.size() - 2; i >= 0; --i) revprod[i] = revprod[i + 1] * seq[i];
set<int> s;
for (int st = 0; st < seq.size(); ++st) {
for (int ed = st; ed < seq.size(); ++ed) {
// cal prod[st]*prod[st+1]*...*prod[ed]
int leftprod(1), rightprod(1);
if (st > 0) leftprod = seqprod[st - 1];
if (ed < seq.size() - 1) rightprod = revprod[ed + 1];
if (s.count(revprod[0] / leftprod / rightprod)) return false;
s.insert(revprod[0] / leftprod / rightprod);
}
}
return true;
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace IP_ColorfulNumber
{
class Program
{
static void Main(string[] args)
{
ColorFul game = new ColorFul();
game.checkifcolorful();
Console.ReadLine();
}
}
class ColorFul
{
public bool checkifcolorful()
{
Console.WriteLine("Enter a number");
String num = Console.ReadLine();
ArrayList product = new ArrayList();
int sum = 0;
for (int i = 0; i < num.Length; i++)
{
if (product.Contains(Convert.ToInt32(num[i]) - 48) || (Convert.ToInt32(num[i]) - 48) == 0 || (Convert.ToInt32(num[i]) - 48) == 1)
{
Console.WriteLine("This number is not colorful");
return false;
}
else
product.Add(Convert.ToInt32(num[i] - 48));
}
for (int i = 0; i < num.Length; i++)
{
sum = Convert.ToInt32(num[i]) - 48;
for (int j = i+1; j < num.Length; j++)
{
if (i == 0 && (Convert.ToInt32(num[j]) - 48) == Convert.ToInt32(num[num.Length - 1]) - 48)
{
}
else
{
sum *= Convert.ToInt32(num[j]) - 48;
if(product.Contains(sum))
{
Console.WriteLine("This number is not coloful");
return false;
}
else
{
product.Add(sum);
}
}
}
}
Console.WriteLine("This number is coloful");
return true;
}
}
}
import java.util.HashMap;
public class Colorful {
public static boolean color(String s1){
String sub,ssub;
int kmer=0, sum = 1, num = 0;
boolean color = true;
HashMap map = new HashMap();
for(int k = 1 ; k<= s1.length(); k++)
{
for(int i = 0 ; i <= (s1.length() - k) ; i++)
{
sub = s1.substring(i, i+k);
if(sub.length()> 0){
for(int j = 0; j<sub.length();j++)
{
ssub = Character.toString(sub.charAt(j));
kmer = Integer.parseInt(ssub);
//System.out.println("Previous product:" +sum+ "Current int:" +kmer);
sum = sum * kmer;
}
}
else
{
kmer = Integer.parseInt(sub);
sum = kmer;
}
//System.out.println(" String: " +sub+ " Product: " +sum);
if (map.containsValue(sum) == false)
{
map.put(sub,new Integer(sum));
}
else
{
System.out.println("Not a Colorful Number!");
color = false;
System.exit(0);
}
sum = 1;
kmer = 0;
}
}
return color;
}
public static void main(String argc[]){
boolean c = color("326");
if(c == true){
System.out.println("Colorful Number!");
}
}
}
I think this method will work and is more efficient I guess. Please do comment to see if it doesnt give desired output.
1. find digits my using / and % operator. eg for 3,2,4,8 for 3248
2. Since for product to be same, one of the digit has to be multiple of other (eg 4 multiple of 2)
3) we shall implement this
for ( i=0;i<no of digits;i++)
int count=0;
for(j=0;j<no of digits;j++)
-> Create a hashmap
if(a[j]%a[i]==0)
if(hashmap.contains(a[j]%a[i])
return false // not a colorful number
else
add in hashmap(a[j]%a[i])
count++;
else
if the digit already exists
return false
else
add the digit as such in hashmap,
if(count>=2) // if some digit divides more than 2 digits i.e. remainder 0
{
repeat the same process of division as above and at some point there will be a clash in hashmap and it will return false
}
Please advise on above solution.
Think this should work
public class test {
public static void main(String[] args){
int num = 235;
String snum = Integer.toString(num);
int length = snum.length();
double amount = Math.pow(2,length);
char[] c = snum.toCharArray();
int[] com = new int[(int) (amount )];
for (int i = 1; i <amount; i++){
String k = Integer.toString(i,2);
if(k.length() <length){
int t = length-k.length();
for(int s=0; s< t;s++){
k="0"+k;
}
}
char[] m = k.toCharArray();
int value = 1;
for (int n = 0; n < length; n++){
if(m[n] == '1'){
value = Integer.parseInt(c[n]+"")*value;
}
}
com[i]=value;
}
boolean check = false;
for(int j =1;j < amount;j++){
int temp =com[j];
com[j]=-1;
for(int l = 1; l < amount; l++){
check=check||(temp==com[l]);
}
}
if(check==false){
System.out.println("colorful");
}
else{
System.out.println("not colorful");
}
}
}
My solution is based on Array structure only.
public class ColorFulNumber {
public ColorFulNumber(int number) {
// TODO Auto-generated constructor stub
if(isColorful(number))
System.out.println(number+" is a colorful number");
else
System.out.println(number+" is not a colorful number");
}
public boolean isColorful(int number) {
if (number < 10)
return true;
String[] sub = new String[getLength(number)];
subNumber(number, sub);
print(sub);
int[] nums = calculateSubNumber(sub);
print(nums);
return isColorful(nums);
}
public boolean isColorful(int[] nums){
for(int i=0; i<nums.length;++i){
for(int j=i+1; j< nums.length; ++j){
if(nums[i] == nums[j])
return false;
}
}
return true;
}
public int[] calculateSubNumber(String[] sub) {
int[] n = new int[sub.length];
for (int i = 0; i < sub.length; ++i) {
n[i] = productOfString(sub[i]);
}
return n;
}
public int productOfString(String number) {
int result = 1;
for (int i = 0; i < number.length(); ++i) {
result = result * Integer.parseInt(number.charAt(i) + "");
}
return result;
}
public void print(Object[] sub) {
for (int i = 0; i < sub.length; ++i)
System.out.print(sub[i] + "--,\t");
System.out.println();
}
public void print(int[] sub) {
for (int i = 0; i < sub.length; ++i)
System.out.print(sub[i] + ",\t");
System.out.println();
}
public void subNumber(int number, String[] sub) {
String n = String.valueOf(number);
int count = 1;
int k=0;
for(;count <n.length();++count){
for(int i=0; (i+count)<= n.length(); ++i){
sub[k] = n.substring(i,i+count);
++k;
}
}
}
public int getLength(int number) {
int result = 0;
for (int i = 2; i <= String.valueOf(number).length(); ++i)
result += i;
return result;
}
}
public boolean colorfulNumber(int number) {
ArrayList<Integer> bag = new ArrayList<Integer>();
int marker;
while(number != 0){
bag.add(number % 10);
number /= 10;
}
if(bag.size() <= 1) { return false;}
marker= bag.size();
for (int i = 1, j = marker-1; i < marker -1;i++,j--) {
int forward = bag.get(i-1) * bag.get(i);
int backward = bag.get(j) * bag.get(j-1);
if(bag.contains(forward) || bag.contains(backward)){
return false;
}else{
bag.add(forward);
bag.add(backward);
}
}
return true;
}
public int colorful(int a) {
String s = String.valueOf(a);
Map<Integer, Integer> map = new HashMap<>();
int temp = 0;
while (temp < s.length()) {
//if immediate next is same return 0
if (map.containsKey(s.charAt(temp) - '0')) return 0;
map.put(s.charAt(temp) - '0', s.charAt(temp) - '0');
temp++;
}
int i = 0;
int j = 1;
int n = s.length();
while (j < n) {
int val1 = s.charAt(i++) - '0';
int val2 = s.charAt(j++) - '0';
if (map.containsKey(val1*val2))
return 0;
map.put(val1 * val2, val1 * val2);
}
return 1;
}
public int colorful(int A) {
HashSet<Integer> hashSet = new HashSet<>();
ArrayList<Integer> numbers = new ArrayList<>();
while (A != 0) {
int num = A % 10;
numbers.add(num);
A /= 10;
}
Collections.reverse(numbers);
int n = numbers.size();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int prod = 1;
for (int k = i; k <= j; k++) {
prod = prod * numbers.get(k);
}
if (hashSet.contains(prod))
return 0;
hashSet.add(prod);
}
}
return 1;
}
public static List<Integer> asListOfDigits(int number) {
return String.valueOf(number)
.chars()
.mapToObj(d -> Integer.valueOf("" + (char) d))
.collect(Collectors.toList());
}
public static boolean isColorful(int number) {
List<Integer> numbers = asListOfDigits(number);
Set<Integer> products = new HashSet<>();
for (int index = 1; index < numbers.size(); index++) {
for (int pos = 0; pos + index <= numbers.size(); pos++) {
Integer product = numbers.subList(pos, pos + index)
.stream()
.collect(Collectors.reducing(1, x -> x, (x, y) -> x * y));
if (!products.add(product)) {
// When add returns false it means the set already contains the element
return false;
}
}
}
return true;
}
O(n^2) solution by first pre-computing the cumulative product array (in O(n)) and then iterating over all subsequences (pairs of start and end indices) and computing their products in O(1) time:
public static boolean isColorful(int number) {
// pre-compute cummulative product array (while breaking number into digits)
String strNum = String.valueOf(number);
// first element is set to 1 so we don't have to deal with edge cases later
int[] cumProd = new int[strNum.length() + 1];
int i = 0;
cumProd[i++] = 1;
for (char c : strNum.toCharArray()) {
cumProd[i] = (c - '0')*cumProd[i - 1];
i++;
}
// now for computing the product of subsequence (start, end] (start exclusive, end inclusive)
// we simply need to compute cumProd[end]/cumProd[start] in O(1) time
Set<Integer> prods = new HashSet<>();
// since start is exclusive (i.e. not included in the product computed by cumProd[end]/cumProd[start])
// this is where the first element in cumProd we set earlier becomes useful
for (int start=0; start < cumProd.length - 1; start++) {
for (int end=start + 1; end < cumProd.length; end++) {
int prod = cumProd[end]/cumProd[start];
if (prods.contains(prod)) return false;
prods.add(prod);
}
}
return true;
}
O(n^2) solution by first pre-computing the cumulative product array (in O(n)) and then iterating over all subsequences (pairs of start and end indices) and computing their products in O(1) time:
public static boolean isColorful(int number) {
// pre-compute cumulative product array (while breaking number into digits)
String strNum = String.valueOf(number);
// first element is set to 1 so we don't have to deal with edge cases later
int[] cumProd = new int[strNum.length() + 1];
int i = 0;
cumProd[i++] = 1;
for (char c : strNum.toCharArray()) {
cumProd[i] = (c - '0')*cumProd[i - 1];
i++;
}
// now for computing the product of subsequence (start, end] (start exclusive, end inclusive)
// we simply need to compute cumProd[end]/cumProd[start] in O(1) time
Set<Integer> prods = new HashSet<>();
// since start is exclusive (i.e. not included in the product computed by cumProd[end]/cumProd[start])
// this is where the first element in cumProd we set earlier becomes useful
for (int start=0; start < cumProd.length - 1; start++) {
for (int end=start + 1; end < cumProd.length; end++) {
int prod = cumProd[end]/cumProd[start];
if (prods.contains(prod)) return false;
prods.add(prod);
}
}
return true;
}
Not my own answer but I saw an answer that suggests you generate the digits to multiply via power sets of the digits. I think this implies that the order of the digits in the sequence doesn't matter for the colorful test (even though the actual products may vary from sequence to sequence). Question 1 is: is really it true that the order of the digits doesn't matter for the test? Question 2 is: and if it is true, how do you prove it?
- Sathish October 27, 2014