Epic Systems Interview Question
Developer Program EngineersCountry: United States
Interview Type: Written Test
This is my code. for each number with N digit, it takes O(N^2) to check if it is additive number.
class AdditiveNumber {
public List<Integer> getAdditiveNumber(int rangeBegin, int rangeEnd) {
List<Integer> list = new LinkedList<>();
for (Integer i = rangeBegin; i <= rangeEnd; i++) {
if (isAdditive(i)) {
list.add(i);
}
}
return list;
}
//returns the number of digits in an integer
private int getLength(int number) {
return (int) (Math.floor(Math.log(number) / Math.log(10)) + 1);
}
//MSD: Most Significant Digit
//returns a number insise "number"
//starting from MSD and end at LSD both inclusive
private int getNumber(int number, int MSD, int LSD) {
if (LSD < 1 || MSD < 1 || MSD < LSD) {
return -1;
}
number %= (int) (Math.pow(10, MSD));
number /= (int) (Math.pow(10, LSD - 1));
return number;
}
//Checked if num1 starts with num2 meaning
//num1 MSDs are equal to num2
private boolean startsWith(int num1, int num2) {
int len1 = getLength(num1);
int startNumber = getNumber(num1, len1, len1 - getLength(num2));
return startNumber == num2;
}
public boolean isAdditive(int number) {
int len = getLength(number);
for (int i = len; i > 2; i--) {
for (int j = i - 1; j > 1; j--) {
int num1 = getNumber(number, len, i);
int num2 = getNumber(number, i - 1, j);
int num3 = getNumber(number, j - 1, 1);
if (startsWith(num3, num1 + num2)) {
number = getNumber(number, j - 1 - getLength(num1 + num2), 1);
if (number == -1) {
return true;
}
} else {
return false;
}
}
}
return false;
}
}
I realized the method isAdditive had some issue with two gigitbase additive numbers. I fixed it. Please replace isAdditive with this code:
public boolean isAdditive(int number) {
int len = getLength(number);
for (int i = len; i > 2; i--) {
for (int j = i - 1; j > 1; j--) {
int num1 = getNumber(number, len, i);
int num2 = getNumber(number, i - 1, j);
int num3 = getNumber(number, j - 1, 1);
if (startsWith(num3, num1 + num2)) {
int number2 = getNumber(number, j - 1 - getLength(num1 + num2), 1);
if (number2 == -1) {
return true;
}else{
if(isAdditive(number2))
return true;
}
}
}
}
return false;
}
void additive(int n)
{
stringstream ss;
ss << n;
string s = ss.str();
int substrLen = 1;
int index=0;
while((substrLen * 3) <= s.length())
{
while(index < s.length())
{
string op1 = s.substr(index,substrLen);
string op2 = s.substr(index+op1.length(),substrLen);
string op3 = s.substr(index+op1.length() + op2.length(),substrLen);
if(stoi(op1) + stoi(op2) == stoi(op3))
printf("\n%s + %s = %s",op1.c_str(),op2.c_str(),op3.c_str());
index += substrLen*3;
}
index = 0;
substrLen++;
}
}
import java.util.ArrayList;
import java.util.Stack;
public class AdditiveNumbers{
public static void main(String[] args)
{
//int number = 123459;
//int number = 123456579;
int number = 123459729;
Stack<Integer> s = new Stack<Integer>();
int div = number;
int quotent = 0;
int number_digit = 0;
// calculating number of digits in the number
while(div!=0)
{
quotent = div%10;
s.push(quotent);
div = div/10;
number_digit++;
}
// inserting the number in the original format in array from stack
int num[] = new int [number_digit];
for(int i=0; i<number_digit;i++)
num[i] = s.pop();
//System.out.println(number_digit);
// calculating the number possible of digit we can allocate in each part i.e a can 1 of a can be 12
int i = 0;
ArrayList<Integer> list = new ArrayList<>();
for(i=1;i*3<=number_digit;i++)
{
int j = i*3;
if(number_digit%j==0)
list.add(i);
}
boolean flag = true;
for(int x=0; x<list.size(); x++)
{
i = list.get(x);
flag = true;
for(int j=0; j<num.length;)
{
int a=0,b=0,c=0;
for(int k=i-1; k>=0; k--)
{
a = (int) (a + Math.pow(10, k)*num[j++]);
}
for(int k=i-1; k>=0; k--)
{
b = (int) (b + Math.pow(10, k)*num[j++]);
}
for(int k=i-1; k>=0; k--)
{
c = (int) (c + Math.pow(10, k)*num[j++]);
}
System.out.println(a+" ,"+b+" ,"+c);
if(a+b!=c)
{
flag = false;
break;
}
}
if(flag==true)
break;
}
if(flag==true)
System.out.println("Yes");
else
System.out.println("No");
}
}
private boolean isAdditive(String num){
if(num.length() % 3 != 0){
return false;
}
for (int i=1; i<= num.length()/3; i++){
int j=0; boolean flag = true;
while(j < num.length()){
int a = Integer.parseInt(num.substring(j, j + i));
j = j+i;
int b = Integer.parseInt(num.substring(j , j+i));
j = j+i;
int c = Integer.parseInt(num.substring(j, j+i));
j=j+i;
if(c != a+b){
flag = false;
break;
}
}
if(flag){
return true;
}
}
return false;
}
private boolean isAdditive(String num){
if(num.length() % 3 != 0){
return false;
}
for (int i=1; i<= num.length()/3; i++){
int j=0; boolean flag = true;
while(j < num.length()){
int a = Integer.parseInt(num.substring(j, j + i));
j = j+i;
int b = Integer.parseInt(num.substring(j , j+i));
j = j+i;
int c = Integer.parseInt(num.substring(j, j+i));
j=j+i;
if(c != a+b){
flag = false;
break;
}
}
if(flag){
return true;
}
}
return false;
}
So does this mean we find all possible combinations?
- John April 18, 2015In the example we have 314538. The answer is 3+1 = 4 and 5 + 3 = 8.
Does this mean we don't care fore 1 + 4 = 5 because 3,1, and 4 is used? Or do we have to find everything everything and we just missed 1 in this example?