## Epic Systems Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
7
of 7 vote

``````public static boolean isColorful(int number){
if(number < 10) return true;

String colorString = String.valueOf(number);
int length = colorString.length();

List<Integer> colorMap = new ArrayList<Integer>();

for(int i =  1; i < length; i++){
for (int j = 0;  j+i <= length; j++){
String sub = colorString.substring(j, j+i);
int product = getProduct(Integer.parseInt(sub));
if(colorMap.contains(product)) return false;
else{
}
}
}
return true;
}

private static int getProduct(int digits) {
if(digits < 10) return digits;
int num = digits;
int product = 1;
while(num > 0){
product = product * (num % 10);
num = num / 10;
}
return product;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think without adding the condition for 0 or 1, the above code will produce correct output

Comment hidden because of low score. Click to expand.
1
of 1 vote

Wont your code include 36 combination in number 326, which is invalid....

Comment hidden because of low score. Click to expand.
0

Wont your code also consider combination 36 in 326, which is not correct..

Comment hidden because of low score. Click to expand.
0

This is O(n^3). There is a better one with O(n^2) use dynamic programming.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}
ArrayList<Integer> newProducts = new ArrayList<Integer>(cache.size());
for(Integer oldProd : cache){
Integer newProd = oldProd * digit;
if(cache.contains(newProd)){
return false;
}
}
}
return true;
}

private static int[] computeDigits(int number){
ArrayList<Integer> digitsList = new ArrayList<Integer>();
while(number > 0){
number /= 10;
}
int[] results = new int[digitsList.size()];
for(int i = 0; i < results.length; i++){
results[i] = digitsList.get(i);
}
return results;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````'''
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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

Why is there any need too recalculate the same product. One you see a same product you return false? Don't understand why storing products would help

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)+"");
}

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--;
}
return false;
}
}
}

return true;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
}
}
}
System.out.println(st1);
Set<Integer> set = new HashSet<Integer>(st1);
if(set.size() < st1.size())
{
return false;
}
else{return true;}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int length = int (Math.log10(n)+1);

int A[length-1];

int b = 10;
for (i=0,i<length,i++){
A[i]=number%b;
b=b*10;
}

int product[length*length];
for (i=0,i<length-1,i++){
for(j=0;j<length-i,j++)
product[j] = A[i]*A[i+j+1];
}

Then compare each product element with others

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int length = int (Math.log10(n)+1);

int A[length-1];

int b = 10;
for (i=0,i<length,i++){
A[i]=number%b;
b=b*10;
}

int product[length*length];
for (i=0,i<length-1,i++){
for(j=0;j<length-i,j++)
product[j] = A[i]*A[i+j+1];
}

Then compare each product element with others``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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];
for(int j = i + 1; j <= lengthOfNumber - 1; j++ ){
product = product * numbers[j];
}
}
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);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package ProblemSolving;

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 {
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{
}
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("Colorful number");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();

}
}

class ColorFul
{
public bool checkifcolorful()
{
Console.WriteLine("Enter a number");

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
}

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
{
}
}
}
}

Console.WriteLine("This number is coloful");

return true;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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!");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
count++;
else
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
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean colorfulNumber(int number) {

ArrayList<Integer> bag = new ArrayList<Integer>();

int marker;
while(number != 0){
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{
}
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why we need DP and complex logics? Is it the requirement or any test cases needs to be covered?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``Why we need DP and other complex solutions. Is it fulfils the requirement or any test cases needs to be covered?``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int colorful(int A) {
HashSet<Integer> hashSet = new HashSet<>();
ArrayList<Integer> numbers = new ArrayList<>();

while (A != 0) {
int num = A % 10;
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;

}
}

return 1;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could someone please explain this to me - the problem states:

"326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12."

Why is 326 not colorful, even though 6 != 12 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));

// When add returns false it means the set already contains the element
return false;
}
}
}

return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
return true;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.