Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
I found the while loop is not right. Taking 263 as an example. So the first loop push 3 in the list. The second loop push 6*3 in the list. The third loop push 2*3 and 2*6*3 in the list. However, as stated in the problem, 2*3 should not be considered, since it is not a substring.
Correct me if I'm wrong.
the code works fine. notice when variable index updated.
second iteration push 6*3 and 6 and in this case index is 1. thrid iteration push 2*6*3, 2*6 and 2.
Take 263 as an example. Shouldn't we also consider the substrings 26 and 63?
Take another example 2634, 63 and 34 are also substrings.
I don't see how this solution takes care of these cases. Did I miss something here? Thanks.
Observe:
* If 263 is colorful then 362 is also colorful.
* Consider all substring ending at index i, for 362, when we are at 3, we have only one option: 3. When we are at 6, we have two options: 3*6 and 6. When we are at 2, we have three options: 2, 6*2 and 3*6*2. Notice how those options populate from one index to the next index. Once we have all those options, we simply use a set or map or whatever counting container to check duplication.
Since there are at least O(N^2) substrings, time complexity is at least O(N^2).
bool color(int num) {
if (num < 10) return true;
set<int> s;
vector<int> v;
while (num) {
int lastdigit = num % 10;
num /= 10;
for (auto &i : v) i *= lastdigit;
v.push_back(lastdigit);
for (auto i : v) {
if (s.count(i)) return false;
else s.insert(i);
}
}
return true;
}
Playable version at:
ideone.com/UxES9I
// Simple solution in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int number = 0;
vector<int> digits;
vector<int> products;
cout << "Enter your number: ";
cin >> number;
int num = number;
while(!(num < 10)){
int temp = num % 10;
digits.push_back(temp);
num /= 10;
}
digits.push_back(num);
std::reverse(digits.begin(), digits.end());
int size = digits.size();
for (int i = 0; i < size; ++i){
for (int j = i + 1; j < size; ++j){
digits.push_back(digits.at(i) * digits.at(j));
}
}
cout << "\nThe vector looks like:\n";
for (vector<int>::iterator i = digits.begin(); i != digits.end(); ++i)
{
cout << *i << " ";
if (*i == 1){
cout << "\nThe number " << number << " is not a colorful number.";
return 0;
}}
for (vector<int>::iterator i = digits.begin(); i != digits.end(); i++){
for (vector<int>::iterator j = i + 1; j != digits.end(); j++){
if (*i == *j){
cout << "\nThe number " << number << " is not a colorful number.";
return 0;
cout << "\nThe number " << number << " is a colorful number.";
return 0;
}
i think this problem should not be that complicated.
first of all, the max number of digits should be 10. because then there must be some repeated digit and if some number is 22, then it has duplicated products (which are 2 and 2), and thus not colourful.
second, if there is 0 in the digits, then it is not colourful: eg, 140 => 1*4*0 = 0
and then, we only need to find the pairs of numbers that will have the same product, which are only a few:
2*3 and 6, 2*4 and 8, 2*6 and 3*4, 3*6 and 2*9.
i.e, check if we have these consecutive numbers.
therefore we only check if above conditions to determine if a number is colourful.
-----------------------
however, i wrote a code not using the idea i mentioned. it's more general i guess orz
in the code i put the number into an int array.
#include <stdio.h>
#include <iostream>
using namespace std;
bool findProductPair(int *arr, int i, int product, int len)
{
int cur = i, prod = product;
if(cur >= len) return false;
if(arr[cur] == prod){
return true;
}
while(cur< len && arr[cur]!=0 && prod % arr[cur] == 0 ){
if( prod == arr[cur] ){
return true;
}
prod = (int)prod / arr[cur];
cur++;
}
return findProductPair(arr, i+1, product, len);
}
int main(void)
{
int arr[3] = {2,6,3};
int len = sizeof(arr)/sizeof(int);
for (int i=0; i < len; i++){
int product = 1;
int j = i;
while(j < len){
product *= arr[j];
if(findProductPair(arr, j+1, product, len)){
cout << " found same pair of product. Not colorful" << endl;
return 1;
}
j++;
}
}
cout << "this is a colorful number" << endl;
return 0;
}
Your idea is cool, but how to deal with such number like 2136? There is a consecutive sequence 2,1,3, and there product is equal to 6.
Your idea is cool, but how to deal with such number like 2136? There is a consecutive sequence 2,1,3, and there product is equal to 6.
i wrote a simple java code for this
boolean isColorful(String number){
char c[] = number.toCharArray();
int[] num = new int[c.length];
int product = 1;
Set<Integer> set = new HashSet<Integer>();
if(c.length > 10)
return false;
for(int i=0; i<c.length; i++){
num[i] = Character.getNumericValue(c[i]);
}
for(int i=0; i<num.length; i++){
System.out.println(set.toString());
product = product * num[i];
if(num[i] == 0 || num[i] == 1)
return false;
if(!set.add(num[i]))
return false;
if(i<(num.length-1))
if(!set.add(num[i]*num[i+1]))
return false;
if(i==(num.length-1))
if(!set.add(product))
return false;
}
System.out.println(set.toString());
return true;
}
package epic;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/*Determine whether a number is colorful or not. 263 is a colorful number because (2,6,3,2x6,6x3,2x3x6) are all different whereas 236 is not because (2,3,6,2x3,3x6,2x3x6) have 6 twice. So take all consecutive subsets of digits, take their product and ensure all the products are different*/
public class colorfulNumber {
boolean isColorful(String number){
int len=number.length();
ArrayList<Integer> intarray = new ArrayList<Integer>();Integer val = null;
if (number != null) {
for (int i = 0; i < len; i++)
intarray.add(Integer.parseInt(String.valueOf(number.charAt(i))));
}
if(intarray.size()==2 ||intarray.size()>10 ||intarray.contains(0)||intarray.contains(1))
return false;
Set<Integer> set = new HashSet<Integer>(intarray);
//Check if the number contains duplicates
if(set.size() < intarray.size())
return false;
else{
for(int i=0;i<intarray.size();i++){
set.add(intarray.get(i));
}
for(int i=0;i<=intarray.size()/2;i++){
val=intarray.get(i)*intarray.get(i+1);
boolean value =set.add(val);
if(!value) return false;
}}
return true;
}
public static void main(String arg[]){
colorfulNumber c=new colorfulNumber();
System.out.println(c.isColorful("263"));
}}
bool colorful(int num){
deque<int> bits;
if(num == 0)
return true;
while(num != 0){
bits.push_front(num % 10);
num /= 10;
}
vector<int> products;
vector<int>::iterator iter;
for(int i = 0; i < bits.size(); i++){
for(int j = 0; j + i < bits.size(); j++){
//cout << " j = " << j << endl;
int product = 1;
int cnt = 0;
while(cnt <= i){
product *= bits.at(j + cnt);
cnt++;
}
iter = find(products.begin(), products.end(), product);
if(iter != products.end()){
cout << *iter << " has already existed " << endl;
return false;
}
else
products.push_back(product);
}
}
return true;
}
public class Color {
public static void main(String args[])
{
int i=1234;
int h=0;
int y=0;
String s = Integer.toString(i);
int[] st=new int[s.length()];
int[] store=new int[s.length()*2];
int p;
do
{
p=i%10;
i=i/10;
if(p!=0)
{
st[h]=p;
System.out.println(st[h]);
h++;
}
}
while(p!=0);
while(y<(s.length()*2))
{
if(y<s.length())
{
store[y]=st[y];
System.out.println(" first: "+store[y]);
}
else
{
for(int b=1;b<=(s.length()-1);b++)
{
store[y]=st[b]*st[b-1];
System.out.println(" second: "+store[y]);
y++;
}
System.out.println(y);
store[y]=1;
for(int k=0;k<=s.length()-1;k++)
{
store[y]=store[y]*store[k];
System.out.println(" third: "+store[y]);
}
}
y++;
}
int[] stnew=new int[s.length()*2];
int l=0;
for(int k=0;k<=((s.length()*2)-1);k++)
{
for(int j=0;j<=k;j++)
{
if(store[k]==store[j]&&k!=j)
{
l++;
}
}
if(l==0)
{
System.out.println(" hey :"+store[k]);
}
l=0;
}
}
}
public class Color {
public static void main(String args[])
{
int i=1234;
int h=0;
int y=0;
String s = Integer.toString(i);
int[] st=new int[s.length()];
int[] store=new int[s.length()*2];
int p;
do
{
p=i%10;
i=i/10;
if(p!=0)
{
st[h]=p;
System.out.println(st[h]);
h++;
}
}
while(p!=0);
while(y<(s.length()*2))
{
if(y<s.length())
{
store[y]=st[y];
System.out.println(" first: "+store[y]);
}
else
{
for(int b=1;b<=(s.length()-1);b++)
{
store[y]=st[b]*st[b-1];
System.out.println(" second: "+store[y]);
y++;
}
System.out.println(y);
store[y]=1;
for(int k=0;k<=s.length()-1;k++)
{
store[y]=store[y]*store[k];
System.out.println(" third: "+store[y]);
}
}
y++;
}
int[] stnew=new int[s.length()*2];
int l=0;
for(int k=0;k<=((s.length()*2)-1);k++)
{
for(int j=0;j<=k;j++)
{
if(store[k]==store[j]&&k!=j)
{
l++;
}
}
if(l==0)
{
System.out.println(" hey :"+store[k]);
}
l=0;
}
}
}
Java solution, with pre-screening based on the idea from @yvette:
public static boolean isColorful(int input){
String inputStr = String.valueOf(input);
int numDigit = inputStr.length();
int[] digits = new int[numDigit];
boolean[] hit = new boolean[10];
for (int i=0; i<numDigit; ++i){
digits[i] = inputStr.toCharArray()[i] - 48; // ascii codec for num starts from 48
if (digits[i]==0){return false;}
if(hit[digits[i]]){
return false;
}else{
hit[digits[i]] = true;
}
}
int multiplyResult;
boolean[] duplicated = new boolean[72];
for (int i=1; i <= numDigit; ++i){ // moving window size
for (int j=0; j < numDigit-i + 1; ++j){ // moving right bound
multiplyResult = 1;
for (int k=j; k < j+i; ++k){ // actually index
multiplyResult *= digits[k];
}
if (duplicated[multiplyResult]){
return false;
} else {
duplicated[multiplyResult] = true;
}
}
}
return true;
}
Sorry wrong parameter for the boolean array 'duplicated', which should be '9!'.
public static boolean isColorful(int input){
String inputStr = String.valueOf(input);
int numDigit = inputStr.length();
int[] digits = new int[numDigit];
boolean[] hit = new boolean[10];
for (int i=0; i<numDigit; ++i){
digits[i] = inputStr.toCharArray()[i] - 48; // ascii codec for num starts from 48
if (digits[i]==0){return false;}
if(hit[digits[i]]){
return false;
}else{
hit[digits[i]] = true;
}
}
int multiplyResult;
boolean[] duplicated = new boolean[362880];
for (int i=1; i <= numDigit; ++i){ // moving window size
for (int j=0; j < numDigit-i + 1; ++j){ // moving right bound
multiplyResult = 1;
for (int k=j; k < j+i; ++k){ // actually index
multiplyResult *= digits[k];
}
if (duplicated[multiplyResult]){
return false;
} else {
duplicated[multiplyResult] = true;
}
}
}
return true;
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
C# code
I calculate the product of the consecutive subsets of digits, then search the product in the remain part of the int array. for example 2*4 =8 , then search whether 8 exists.
public class Program
{
public static bool sameDigit(int[] a, int product, int i, int j,int len)
{
int curFront = i;
int curEnd = j;
// search the fromt part
for (int m = 0; m < curFront; m++)
{
if (a[m] == product)
return true;
}
// serch the end part
for (int n = curEnd + 1; n < len; n++)
{
if (a[n] == product)
return true;
}
return false;
}
public static bool colorfulNum(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int product = 1;
for (int j = i; j < a.Length; j++)
{
product *= a[j];
// as no digit is greater than 10
if (product > 10)
break;
else
{
if (a[j] == 0 || a[j] == 1 || sameDigit(a, product, i,j, a.Length))
{
Console.WriteLine("found same pair of product. Not colorful");
return false;
}
}
}
}
Console.WriteLine("this is a colorful number");
return true;
}
static void Main(string[] args)
{
int[] a = {3,5,4,2 };
bool b = colorfulNum(a);
Console.WriteLine(b);
}
}
package com.star.epic;
import java.util.HashSet;
import java.util.Set;
/*
* Determine whether a number is colorful or not.
* 263 is a colorful number because (2,6,3,2x6,6x3,2x3x6) are all different
* whereas 236 is not because (2,3,6,2x3,3x6,2x3x6) have 6 twice.
* So take all consecutive subsets of digits,
* take their product and ensure all the products are different.
*/
public class Colorful {
public static boolean is_color(int num) {
String str = String.valueOf(num);
char digits[] = str.toCharArray();
int length = str.length();
int i = 1;
Set set = new HashSet();
// i is the number of consecutive number
int value = 1;
while (i <= length) {
System.out.println("get " + i + " consecutive number");
int m = 0;
while (m <= length - i) {
System.out.print("start from index "+m+" ,we get ");
int j = 0;
value = 1;
//get value from a[m] to a[m+j]
while (j < i) {
System.out.print(digits[m + j] - 48+" ");
value = value *(digits[m + j] - 48);
j++;
}
System.out.println();
if(set.contains(value)){
return false;
}else{
set.add(value);
}
m++;
}
System.out.println();
i++;
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int number = 263;
System.out.println(is_color(number));
number = 236;
System.out.println(is_color(number));
}
}
Simple C++ code
#include<iostream>
using namespace std;
bool colorful(int *,int );
int main()
{
int number = 0;
int *a = new int[10];
memset(a,NULL,10);
int i=1;
char num_length[10];
cout<<"Enter number"<<endl;
cin>>number;
itoa(number,num_length,10);
while(number>0)
{
a[strlen(num_length)-i] = number%10;
number = number/10;
++i;
}
for(int i=0;i<strlen(num_length);i++)
{
if(a[i] == 1 || a[i] == 0 )
{
cout<<"Not a colorful number"<<endl;
delete []a;
return 0;
}
}
bool result = colorful(a, strlen(num_length));
if(result)
cout<<"Colorful"<<endl;
else
cout<<"Not a colorful number"<<endl;
delete []a;
return 0;
}
bool colorful(int *a,int length)
{
int i=0,temp=length;
while(1)
{
a[temp]=a[i]*a[i+1];
temp++;
i++;
if(i==length-1)
break;
}
a[temp]=1;
for(int i =0;i<=temp;i++)
a[temp]=a[temp]*a[i];
int j =0,check ;
while(j<temp)
{
check = a[j];
for(int i=j+1;i<=temp;i++)
{
if(check == a[i] )
return false;
}
++j;
}
return true;
}
#include<iostream>
#include<conio.h>
#include<string>
#include<vector>
using namespace std;
int length;
int num[100];
vector<int> array;
void is_colour(int k);
int main()
{
int a=236,i=0;
cout<<a<<" is ";
while(a>10)
{
int temp=a%10;
num[i]=temp;
array.push_back(temp);
a=a/10;
i++;
}
num[i]=a;
array.push_back(a);
length=i;
// To calculate the values
for(int k=1;k<length+1;k++)
{
is_colour(k);
}
bool flag=true;
for(vector<int>:: iterator m=array.begin();m!=array.end();m++)
{
for(vector<int>:: iterator n=m+1;n!=array.end();n++)
{
if( *m==*n)
{
flag=false;
break;
}
}
}
if(flag==false)
cout<<"Not colourful";
else
cout<<"Colourful";
getch();
return 0;
}
void is_colour(int k)
{
for(int i=0;i<length;i++)
{
int product=1;
int m=i;
for( int count=0;count<k+1;m++,count++)
{
product*=num[m];
}
if(m<length+2)
array.push_back(product);
}
}
static boolean iscolorful(int num)
{
ArrayList<Integer> s=new ArrayList<Integer>();
int x=num;
int i=0;
while(x>0)
{s.add(x%10);
x=x/10;
i++;}
int a[]= new int[i];
Iterator<Integer>i1= s.iterator();
while(i1.hasNext())
{a[i-1]=i1.next();
i--;
}
int d=s.size();
i=2;
while(i<=d)
{int x1=0;
while((x1+i)<=d)
{int mult=1;
for(int j=0;j<i;j++)
mult=mult*a[x1+j];
if (s.contains(mult))
return false;
else
s.add(mult);
x1++;
}
i++;
}
for (int i11=0;i11<s.size();i11++)
System.out.print("Set:"+s.get(i11));
System.out.println();
return true;
}
public static boolean isColorful(int num)
{
ArrayList<Integer> list = new ArrayList<Integer>(); // contains each digit in num
int key = 0; // key value for the hashtable
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
while(num != 0)
{
list.add(num%10);
if(table.contains(num%10))
{
return false;
}
else
{
table.put(key++, num%10);
System.out.println(num%10);
num /= 10;
}
}
int listSize = list.size();
int[] array = new int[listSize]; // contains the products of each substring
for(int i = 0; i < listSize; ++i)
{
array[i] = list.get(i);
}
int start = 1;
while(start < listSize - 1) // calculate the product of all substrings, O(n^2) where n is the number of digits
{
int j = 0;
for(int i = start; i < listSize; ++i)
{
array[j] = array[j] * list.get(i);
if(table.contains(array[j]))
{
return false;
}
else
{
table.put(key++, array[j]);
System.out.println(array[j]);
++j;
}
}
++start;
}
return true;
}
Heh guys kindly clarify my doubt in this question...
Question says that the product of substrings must be unique if the number has to be said colorful.
For a number "263", the subsets are { 2,6,3,26,23,63,263}. As the problem suggests should we find the product between substrings(i.e 26*23, 63*263......) or within the substring itself(i.e., 2*6,2*3,6*3,2*6*3) ?!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int n,r,s;
scanf("%d",&n);
int a[82];
memset(a, 0, sizeof(a));
while(n>10)
{
r=n%10;
s=(n%100)-r;
s=s/10;
if(a[r*s]>0)
{
printf("The no is not colorful");
return 0;
}
else
a[r*s]=1;
n=n/10;
}
printf("The no is colorful");
return 0;
}
Its the most eficient way i can think of..it does in order log n-1 where log is of base 10..:)
Your code is perfectly fine, but u forgot the case of single digits, i.e 2,6,3 in a[2],a[6],a[3] as 1, and
u can add one simple case ,if either r or s is one at any point of time then it is not colourful becoz 1*anynumber = anynumber.
#include "stdio.h"
#include "conio.h"
int main(){
int n=246;
int a[10]={0};
int b[10]={0};
int flag=1;
int end=0,last=0,i,j,num;
while(n){
a[end]=n%10;
n=n/10;
end++;
}
for(i=0;i<end;i++){
num=1;
for(j=i;j<end;j++){
if(i==0 && j==end-1)
continue;
num=num*a[j];
//printf("\n%d",num);
b[last++]=num;
}
}
//printf("\n");
for(i=0;i<last;i++){
//printf("%d ",b[i]);
}
for(i=0;i<last-1;i++){
for(j=i+1;j<last;j++){
if(b[i]==b[j]){
flag=0;
break;
}
}
if(flag==0)
break;
}
if(flag==0)
printf("\nThe number is not colorful");
else
printf("\nThe number is colorful");
getch();
}
#include <iostream>
#include <map>
#include <vector>
using namespace std;
bool colorful(int num){
int temp = num;
int multi = 1, l = 0;
while(temp){
temp /= 10;
++l;
multi *= 10;
}
multi /= 10;
map<int, int>m;
vector<int>v;
for(int i = 0; i < l; i++){
v.push_back(num/multi);
num %= multi;
multi /= 10;
}
int sum = 1;
for(int i = 1; i <= l; i++){
for(int j = 0; j <= l-i; j++){
sum = 1;
for(int k = 0; k < i; k++)
sum *= v[j+k];
if(m.find(sum) != m.end())
return false;
else
m[sum]++;
}
}
return true;
}
int main()
{
cout <<colorful(263) << endl;
cout <<colorful(236) << endl;
return 0;
}
public static boolean isColorFull(String s) {
Set<Integer> prods = new HashSet<Integer>();
for (int size = 1; size <= s.length(); size++) {
for (int i = 0; i <= s.length() - size; i++) {
String sub = s.substring(i, i + size);
int prodVal = 0;
for (int cnt = 0; cnt < sub.length(); cnt++) {
char curChar = sub.charAt(cnt);
int newVal = 0;
if (Character.isDigit(curChar)) {
newVal = Character.digit(curChar, 10);
} else {
return false;
}
if (cnt == 0) {
prodVal = newVal;
} else {
prodVal *= newVal;
}
}
if (! prods.add(prodVal)) {
return false;
}
}
}
return true;
}
#include<iostream>
#include<string>
using namespace std;
bool is_colorful(string number)
{
int i,j,k,len = number.length();
if(len>7) return false;
for(i=0;i<len;i++) if(number[i] =='0' || number[i] == '1') return false;
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++) if(number[j]==number[i]) return false;
}
for(i=0;i<len;i++)
{
if(number[i]=='2')
{
if(i!=0)
{
switch(number[i-1])
{
case '3':
for(k=0;k<len;k++) if(number[k]=='6') return false;
break;
case '4':
for(k=0;k<len;k++) if(number[k]=='8') return false;
break;
case '6':
for(k=0;k<len-1;k++)
{
if((number[k]=='3' && number[k+1]=='4' )||(number[k]=='4' && number[k+1]=='3')) return false;
}
break;
case '9':
for(k=0;k<len-1;k++)
{
if((number[k]=='3' && number[k+1]=='6' )||(number[k]=='6' && number[k+1]=='3')) return false;
}
break;
}
}
if(i!=len-1)
if(i!=0)
{
switch(number[i+1])
{
case '3':
for(k=0;k<len;k++) if(number[k]=='6') return false;
break;
case '4':
for(k=0;k<len;k++) if(number[k]=='8') return false;
break;
case '6':
for(k=0;k<len-1;k++)
{
if((number[k]=='3' && number[k+1]=='4' )||(number[k]=='4' && number[k+1]=='3')) return false;
}
break;
case '9':
for(k=0;k<len-1;k++)
{
if((number[k]=='3' && number[k+1]=='6' )||(number[k]=='6' && number[k+1]=='3')) return false;
}
break;
}
}
}
}
return true;
}
int main()
{
string A;
cin>>A;
if(is_colorful(A)) cout<<"yes\n";
else cout<<"No\n";
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EpicQ
{
class Program
{
static void Main(string[] args)
{
int i = 0, result=0,count = 0; ;
string s = Console.ReadLine();
i = Convert.ToInt32(s);
List<int> lst = new List<int>();
List<int> empty = new List<int>();
for (int j = 0; j < s.Length; j++)
{
lst.Add(i%10);
i /= 10;
}
lst.Reverse();
for (int h = 0; h < s.Length; h++)
{
if (h != s.Length - 1)
{
result = lst[h] * lst[h + 1];
empty.Add(result);
}
else
{
result = 1;
for (int l = 0; l < s.Length; l++)
{
result *= lst[l];
}
empty.Add(result);
}
}
lst.AddRange(empty);
for (int m = 0;m< lst.Count; m++)
{
for (int n = m + 1; n < lst.Count - 1; n++)
{
if (lst[m] == lst[n])
{
count++;
}
}
}
if (count > 0)
{
Console.WriteLine("not colorful");
}
else
{
Console.WriteLine("colorful");
}
}
}
}
import java.util.HashSet;
import java.util.Set;
public class ColorfulNumber {
public static boolean isColorful(int number) {
String num = String.valueOf(number);
int length = num.length();
int size = 1;
Set<Integer> set = new HashSet<Integer>();
while (size <= length) {
for (int i = 0; i <= length - size; i++) {
int j = size;
int index = 0;
int value = 1;
while (j > 0) {
value *= Integer.parseInt(String.valueOf(num.charAt(i
+ index)));
j--;
index++;
}
if (set.contains(value)) {
return false;
} else {
set.add(value);
}
}
size++;
}
return true;
}
public static void main(String[] args) {
System.out.println(isColorful(263));
}
}
import java.util.ArrayList;
import java.util.Scanner;
public class colorNum {
public static void main(String[] args) {
System.out.println("Please input some numbers: ");
Scanner sc= new Scanner(System.in);
int num=sc.nextInt();
sc.close();
String nums=getEachNum(num);
char[] numbers=nums.toCharArray();
int[] ns=new int[numbers.length];
for(int i=ns.length-1;i>=0;i--){
ns[ns.length-1-i]=numbers[i]-48;
}
check(ns);
}
private static String getEachNum(int num) {
StringBuffer sb=new StringBuffer();
while(num!=0){
int rest=num%10;
sb.append(rest);
num=num/10;
getEachNum(num);
}
String result=sb.toString();
return result;
}
private static void check(int[] nums) {
ArrayList<Integer> al=new ArrayList<Integer>();
for(int i:nums){
al.add(i);
}
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
int multi=1;
for(int k=i;k<=j;k++){
multi*=nums[k];
}
al.add(multi);
}
}
System.out.println(al);
boolean color=true;
for(int i=0;i<al.size()-1;i++){
if(al.get(i)==al.get(i+1)){
color=false;
break;
}
}
if(color==true){
System.out.print("this is a color number");
}else{
System.out.print("this is not a color number");
}
}
}
Here is a working code in C++. I have parsed the number into an array and then continued to form different adjacent subsets of different length. I used another array to store all the different combinatorial products. Finally I just check to see if any duplicate element is preset in the array which stores all the possible products.
#include <cstdio>
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long long int ct=0, temp, num, *arr, i, j, *hash, k, l=0, ct1=0, sum=1, flag=0;
cin>>num;
temp=num;
while (temp!=0)
{
ct++;
temp/=10;
}
arr=new long long int[ct];
temp=num;
i=ct-1;
while (temp!=0)
{
arr[i]=temp%10;
temp/=10;
i--;
}
if (ct%2==0)
{
temp=(ct/2)*(ct+1);
}
else
{
temp=(ct)*((ct+1)/2);
}
hash=new long long int[temp];
for (i=1; i<=ct; i++)
{
for (j=0; j<(ct-i+1); j++)
{
k=j;
ct1=1;
while (ct1<=i)
{
sum*=arr[k];
k++;
ct1++;
}
hash[l]=sum;
l++;
sum=1;
}
}
for (i=0; i<l; i++)
{
for (j=i+1; j<=l; j++)
{
if (hash[i]==hash[j])
{
flag=1;
}
}
if (flag==1)
{
break;
}
}
if (flag==1)
{
cout<<"Not a colorful number"<<endl;
}
else
cout<<"A colorful number"<<endl;
return 0;
}
import java.util.HashSet;
import java.util.Iterator;
class ColorfulNumber {
public static boolean isColorful(int n) {
HashSet<Integer> set = new HashSet<Integer>();
int num = n;
int a = num % 10; // former
num /= 10;
set.add(a);
while (num > 0) {
int b = num % 10; // latter
int c = a * b; // product
if (!set.contains(b)) {
set.add(b);
a = b;
num /= 10;
} else {
return false;
}
if (!set.contains(c)) {
set.add(c);
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println(isColorful(236));
}
}
import java.util.HashSet;
import java.util.Iterator;
class ColorfulNumber {
public static boolean isColorful(int n) {
HashSet<Integer> set = new HashSet<Integer>();
int num = n;
int a = num % 10; // former
num /= 10;
set.add(a);
while (num > 0) {
int b = num % 10; // latter
int c = a * b; // product
if (!set.contains(b)) {
set.add(b);
a = b;
num /= 10;
} else {
return false;
}
if (!set.contains(c)) {
set.add(c);
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println(isColorful(236));
}
}
public boolean colorfulNum(int num) throws Exception{
ArrayList<Integer> numList = new ArrayList<Integer>();
while(num!=0){
numList.add(num%10);
num /= 10;
}
HashSet<Integer> mSet = new HashSet<Integer>(100);
for(int conLen = 1; conLen<=numList.size();conLen++){
for(int start=0;start<=numList.size()-conLen;start++){
int multiple = 1;
for(int next=start;next<conLen+start;next++){
multiple *= numList.get(next);
}
/*if(multiple<0)
throw new Exception("overflow");//overflow*/
if(mSet.contains(multiple)){
return false;
}else{
mSet.add(multiple);
}
}
}
return true;
}
import java.util.*;
public class Colorful{
public static void main(String args[])
{
int n = 236;
ArrayList digList = new ArrayList();
ArrayList digTempList = new ArrayList();
int temp = n;
while(temp >=1){
int a = temp%10;
digList.add(a);
temp = temp/10;
}
Collections.reverse(digList);
temp = 1;
for(int i = 0; i<digList.size();i++){
temp = temp* (int)digList.get(i);
digTempList.add(digList.get(i));
}
for(int i = 0; i<digTempList.size()-1;i++){
digList.add((int)digTempList.get(i) * (int)digTempList.get(i+1));
}
digList.add(temp);
HashSet mySet = new HashSet();
for(int i = 0; i<digList.size()-1;i++){
if(mySet.contains(digList.get(i))){
System.out.println("Number is not colorful");
break;
}else{
mySet.add(digList.get(i));
}
}
}
}
import java.util.ArrayList;
import java.util.HashSet;
public class ColorfulNumber {
public static boolean iscolorfulnumber(int num) {
ArrayList<Integer> list = new ArrayList<Integer>();
int index = 0;
while (num != 0) {
int r = num % 10;
num = num / 10;
int length = list.size();
for (int i = index; i < length; i++) {
list.add(list.get(i) * r);
System.out.println(list.get(i) * r);
}
list.add(r);
System.out.println( r);
index = length;
}
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < list.size();i++) {
if (set.contains(list.get(i))) {
return false;
} else {
set.add(list.get(i));
System.out.println("set add: " + list.get(i) );
}
}
return true;
}
public static void main(String args[]) {
System.out.println(iscolorfulnumber(236));
}
}
public static boolean colorfulNum(int num){
String n = String.valueOf(num);
Set<Integer> products = new HashSet<Integer>();
int l = n.length();
for(int i=0; i<l; i++){
int product = 1;
for(int j=i; j<l; j++){
product *= n.charAt(j)-'0';
if(products.contains(product)) return false;
products.add(product);
}
}
return true;
}
mport java.util.Arrays;
class ColorfulNumber{
public static void main(String args[]){
ColorfulNumber obj = new ColorfulNumber();
System.out.println(obj.isColorful(263));
}
public boolean isColorful(int num){
String number = String.valueOf(num);
System.out.println("number=" + number);
//Create a matrix of number with diagonal elements as digits in the num
//Get the digits from the number
int len = number.length();
int digits[] = new int[len];
for(int i=0; i<len; i++){
digits[i] = number.charAt(i) - '0';
}
print(digits);
int numberSets[][] = new int[len][len];
for(int i=0; i<len;i++){
numberSets[i][i] = digits[i];
}
for(int i=0; i<len; i++){
for(int j=0; j<i; j++){
numberSets[i][j] = numberSets[i-1][j] * digits[i];
}
}
printArr(numberSets);
int lengthOfArray = ((len*len) - len )/2 + len;
System.out.println("Length of new array" + lengthOfArray);
int index=0;
int completeArr[] = new int[lengthOfArray];
for(int i=0; i<len; i++){
for(int j=0; j<=i; j++){
completeArr[index] = numberSets[i][j];
index++;
}
}
Arrays.sort(completeArr);
print(completeArr);
for(int i=0; i<completeArr.length-1; i++){
if(completeArr[i] == completeArr[i+1]){
return false;
}
return true;
}
public void printArr(int [][]arr){
for(int []row: arr){
print(row);
}
}
public void print(int []arr){
System.out.println();
for(int i: arr){
System.out.print(i + "----");
}
System.out.println();
}
}
import java.util.Arrays;
class ColorfulNumber{
public static void main(String args[]){
ColorfulNumber obj = new ColorfulNumber();
System.out.println(obj.isColorful(263));
}
public boolean isColorful(int num){
String number = String.valueOf(num);
System.out.println("number=" + number);
//Create a matrix of number with diagonal elements as digits in the num
//Get the digits from the number
int len = number.length();
int digits[] = new int[len];
for(int i=0; i<len; i++){
digits[i] = number.charAt(i) - '0';
}
print(digits);
int numberSets[][] = new int[len][len];
for(int i=0; i<len;i++){
numberSets[i][i] = digits[i];
}
for(int i=0; i<len; i++){
for(int j=0; j<i; j++){
numberSets[i][j] = numberSets[i-1][j] * digits[i];
}
}
printArr(numberSets);
int lengthOfArray = ((len*len) - len )/2 + len;
System.out.println("Length of new array" + lengthOfArray);
int index=0;
int completeArr[] = new int[lengthOfArray];
for(int i=0; i<len; i++){
for(int j=0; j<=i; j++){
completeArr[index] = numberSets[i][j];
index++;
}
}
Arrays.sort(completeArr);
print(completeArr);
for(int i=0; i<completeArr.length-1; i++){
if(completeArr[i] == completeArr[i+1]){
return false;
}
}
return true;
}
public void printArr(int [][]arr){
for(int []row: arr){
print(row);
}
}
public void print(int []arr){
System.out.println();
for(int i: arr){
System.out.print(i + "----");
}
System.out.println();
}
}
import java.util.HashSet;
public class Colorful {
public static void main(String[] args){
int number =236;
System.out.println(number+" is colorful: "+isColorful(number));
}
public static boolean isColorful(int number){
int product=1;
String numString = String.valueOf(number);
HashSet<Integer> products = new HashSet<Integer>();
int numOfProducts=0;
for(int i=0;i<numString.length()-1;i++){
products.add(Integer.parseInt(numString.substring(i,i+1)));
products.add(Integer.parseInt(numString.substring(i,i+1))*Integer.parseInt(numString.substring(i+1,i+2)));
product*=Integer.parseInt(numString.substring(i,i+1));
numOfProducts+=2;
}
//handle last number
product*=Integer.parseInt(numString.substring(numString.length()-1,numString.length()));
products.add(product);
products.add(Integer.parseInt(numString.substring(numString.length()-1,numString.length())));
numOfProducts+=2;
if(numOfProducts==products.size()){
return true;
}else{
return false;
}
}
}
When it is said that we need consecutive subsets, why is that in the example of 263 where we have subsets of [ (2,6,3) ], we are omitting the subset value of (2 * 3) and wy not (2x3x6) ?
regards,
Oj
- Anonymous August 24, 2012