## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
19
of 21 vote

I think the key of this problem is to determine the initial first number and the second number. once it's decided, other numbers are automatically generated.

Below code is not optimized, but should work.

``````/// <summary>
///     1. all zero - 00000
///     2. starting with zero - 0112
///     3. zero in the middle
/// </summary>
/// <param name="text"></param>
/// <returns></returns>
static bool IsAggregatedNumber(string text)
{
for (var i = 1; i <= text.Length / 2; i++)
{
for (var j = 1; j <= text.Length / 2; j++)
{
if (Match(i, j, text))
{
return true;
}
}
}

return false;
}

static bool Match(int i, int j, string text)
{
var first = text.Substring(0, i);
var second = text.Substring(i, j);
var buffer = new StringBuilder();
buffer.Append(first);
buffer.Append(second);
while (buffer.Length < text.Length)
{
var third = (Int32.Parse(first) + Int32.Parse(second)).ToString();
buffer.Append(third);
first = second;
second = third;
}

return buffer.Length == text.Length && buffer.ToString() == text;
}``````

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

Comment hidden because of low score. Click to expand.
-2

Modified the code a wee bit in java. works for the test cases in the problem

``````static boolean isAggregatedNumber(String text) {
int length = text.length() / 2;
for(int i = 1; i <= length; i++) {
for(int j = 2; j <= length; j++) {
if(Match(i,j,text)) {
return true;
}
}
}
return false;
}

static boolean Match(int i, int j, String text) {
String first = text.substring(0, i);
String second = text.substring(i, i*2);
StringBuilder buffer = new StringBuilder(first);
buffer.append(second);
while(buffer.length() < text.length()) {
Integer x  = (Integer.parseInt(first) + Integer.parseInt(second));
String third =  x.toString();
buffer.append(third);
first = second;
second = third;
}
if(text.equals(buffer.toString()))
return true;
return false;
}``````

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

I think for the sake of the problem, it is better to assume that the second number is greater than the first.

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

It doesn't work. check the case 1121325

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

@Anonymous it works for this case.
it will pass when in match function 1 , 12 will go as the substrings.
so it will become 11213 then 12+13 will happen i.e 1121325.
The solution is absolutely correct

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

@PAN, you modified version has some issues I think:

In the first method named isAggregatedNumber:

``````// issue in this line with initialization of 'j'
for(int j = 2; j <= length; j++) {

/* This can be corrected in either of the two ways: */
// (1) If we allow for 23225 as valid, for ex: 23+2=25,
// where first=23, second=2, and third=25. Do: j=1 (as done by shawn),
for(int j=1; j <= length; j++) {

// (2) If (1) is not allowed and only proper Fibonacci pattern is allowed,
// like 232447 as valid, for ex: 23+24=47,
// where first=23, second=24, and third=47. Do: j=i,
for(int j = i; j <= length; j++) {``````

In the second method named Match:

``````// issue in this line with the 2nd parameter of substring()
String second = text.substring(i, i*2);

// this can be corrected this way
String second = text.substring(i, j);``````

I think shawn's proposed method is doing fine.

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

Shawns solution will return true for any number with even digits, one check to see if any addition is happening needs to be done

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

I think you can skip this check and loops for some cases if you don't let i and j iterate further than textlength / 3 because one addition result needs at least 1/3 of the textlength in space. Not thoroughly checked though.

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

Good job shawn! Here's a working python solution:

``````def find_aggregated_number(A):
for i in range(1,int(len(A)/2)):
for j in range(i+1,int(len(A)*2/3)+1):
if(check_aggregate(i,j,A)):
return True
return False

def check_aggregate(i,j,A):
result = A[0:i] + A[i:j]
first = int(A[0:i])
second = int(A[i:j])

while(len(A) > len(result)):
third = first + second
result = result + str(third)
first = second
second = third
return (len(result)==len(A)) and (result == A)

for A in ["112358","122436","1299111210","112112224"]:
if (find_aggregated_number(A)):
print("{} is an aggregated number".format(A))
else:
print("{} is not an aggregated number".format(A))``````

Comment hidden because of low score. Click to expand.
2
of 4 vote

``````enum {
FALSE,
TRUE
};
/*
* Pass 12345 as array, index = 2, size = 2
* result of this function would be 34.
* Pass 12345 as array, index = 2, size = 3
* result of this function would be 345.
* Pass 12345 as array, index = 1, size = 3
* result of this function would be 234.
*/
int make (int *A, int index, int n)
{
// n is the size
int iterator = index + size - 1;
int sum = 0;
while (iterator >= index)
{
sum = sum * 10 + A[iterator];
iterator--;
}
return sum;
}
int is_Aggregated(int *Array, int size)
{
int factor = 1;
// used to move the indexes through the locations.
int i = 0, j, k;

while (i < n)
{
j = i + factor;
k = j + factor;
if (k >= n )
{
break;
}
if(make(A,i,factor) + make(A,j,factor) !=
make (A,k,factor))
{
i = 0;
factor++;
} else {
if ( k + factor == n){
/*
* The last position is matched, therefore
* the array is a aggregate;
*/
return TRUE;
}
i = i + factor;
}

}
return FALSE;
}

example 1
pass a: 0 1 1 2 3 5 8
i j k
pass b: 0 1 1 2 3 5 8
i j k
pass c: 0 1 1 2 3 5 8
i j k
pass d: 0 1 1 2 3 5 8
i j k
pass e: 0 1 1 2 3 5 8
i j k      ==> true

Example 2

pass a: 1 2 3 4 4 6 8 0
i j k
pass b: 1 2 3 4 4 6 8 0
i j k            ==> i = 0, factor = 2
pass c: 1 2 3 4 4 6 8 0
i   j   k
pass d: 1 2 3 4 4 6 8 0
i   j   k      ==> true

Example 3
pass a: 1 2 3 4 5 6 5 7 9
i j k
pass b: 1 2 3 4 5 6 5 7 9
i j k            ==> i = 0, factor = 2
pass c: 1 2 3 4 5 6 5 7 9
i   j   k          ==> i = 0, factor = 3
pass d: 1 2 3 4 5 6 5 7 9
i     j     k          ==> true``````

---
A mistake is a crash course in learning.
---

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

I think it is a linear solution!!

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

Mistakes
Alg related:
1) After factor variable increases, i should start from 0 instead it starts from factor position. The problem line is "i = i + factor;"
2) make method does not return the sum variable.
Syntax related:
int is_Aggregated(int *A, int n)
4) There should be a ; in line i = 0

Cheers! :)

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

why do you assume that the two numbers that are to be summed have same number of digits?

you program doesn't solve 132411235: 1234+1=1235

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

Corrected. Thanks :)

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

can you check for 1235813 - in this case all your assumptions are valid ( like second is > first number etc).
Your input works only if A is given as { 1,2,3,5,8,13} but not
{ 1,2,3,5,8,1,3}. Correct me if I mistook. If you say you need to input the array as in the second case, you are back to the same problem, how will u partition the array to 13 or 1,3.

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

Agreeing to nikhil simha,

Assuming that the two numbers that are to be summed have same number of digits does not make up for satisfactory solution.

Solution proposed fails to solve example like:
1299111210, because 12+99=111, 99+111=210
1100101, because 1+100=101

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

This code doesn't even compile, and after fixing it, it doesn't solve the following inputs:
1100101
12344680
1299111210

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

I did it recursively in Python:

``````def isAgg(n, path=[]):
#if the input is an integer change it into a string
n=str(n)

#if 1+1=2 in 112358
if len(path)==3 and sum(path[:2]) == path[2]:
#if a+b=c and there is nothing left, return True
if len(n)==0:
#print path, n
return True
#if a+b=c and there is leftover
else:
#print path, n
path.pop(0)
return True and isAgg(n, list(path) )
#if the sum of first two numbers is not the third number, discard the current path
elif len(path)>3:
return False

#for check all possible permutations: 112358 -> isAgg(1, 12358), isAgg(11, 2358), isAgg(112, 358),...
out=False
for i in range(1, len(n)+1):
out |= isAgg(n[i:], path + [int(n[:i])])
return out

print isAgg(112112224)``````

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

I think dynamic programming should be used here. I figured out a recurrence relation to solve this in O(n^5). Does anyone have a better idea?

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

One of the other answers mentions it: the key is to determine the initial first and second numbers, then rest is easy to verify.

There are Theta(n^2) possibilities for the first and second, and O(n) time to verify for each such possiblilty, so there is an O(n^3) algorithm.

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

It doesn't be the case- consider 1125126 - 1 + 125 = 126 but 1+1 could look like they are a good pick for aggregation

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

@gizmo: What part of "there are theta(n^2) possibilities" didn't you understand?

1,1 is one possibility, but fails when you reach 5. So you try another one...

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

Since the constraint is not specified, I will assume the number of digits is ~20. The question asks to divide the number into several parts, so a n-digit number can be divided at at most n-points ( between every two adjacent digits and minus point before first digit ). Hence, use backtrack to iterate through all 2^n possibilities and check for the condition.

Complexity should be O(2^n) and number for index i to index j can be pre-calculated

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

Python version

``````# -*- coding: utf-8 -*-
"""
Created on Sun Nov 25 19:45:26 2012

@author: qzhang
"""
DEBUG = 0

def IsAggregatedNumber(number):
global DEBUG
num_str = str(number)
length = len(num_str)
if DEBUG == 1:
print "length is",length
for i in range(1,length/2+1):
for j in range(1,length/2+1):
if match(i,j,num_str):
return True

return False

def match(i,j,num_str):
global DEBUG
first = num_str[:i]
second = num_str[i:i+j]
buff = ""
buff =buff +first
buff =buff +second

while len(buff) < len(num_str):
if DEBUG ==1:
print "first ", first
print "second ", second
third = str(int(first) + int(second))
if DEBUG ==1:
print "third ", third
buff =buff +third
first = second
second = third

if(cmp(buff,num_str) == 0):
return True
else:
return False

if __name__ == "__main__":
print IsAggregatedNumber(112358)
print IsAggregatedNumber(1224)
print IsAggregatedNumber(1299111210)
print IsAggregatedNumber(112112224)``````

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

My solution in Java. Also created an amount of unit tests.
Also works for very big numbers (see last Unit Test), using BigInteger.

``````import java.math.BigInteger;

public class AggregatedNumber {
public boolean testNumber(String number) {
if (number.length() <= 2) {
return true;
}

// Find j: the position of the second pointer
for(int j = 1; j < number.length() - 1; j++) {
String number1String = number.substring(0, j);
if (number1String.length() > 1 && number1String.charAt(0) == '0') {
continue;
}
BigInteger number1 = new BigInteger(number1String);

// Find jLength: The length of the second value
for(int jLength = j; jLength < number.length() - j; jLength++) {
String number2String = number.substring(j, j + jLength);
if (number2String.length() > 1 && number2String.charAt(0) == '0') {
continue;
}
BigInteger startTwo = new BigInteger(number2String);

// Check if the combination {j, jLength} results in an aggregated number
if (check(number1, startTwo, number.substring(number1String.length() + number2String.length()))) {
return true;
}
}
}

// We did not find any valid combination of {j, jLength}: return false
return false;
}

private boolean check(BigInteger number1, BigInteger startTwo, String numberSubstring) {
if (numberSubstring.isEmpty()) {
// We are finished
return true;
}

// What do we expect next? The previous two numbers added
String expectedString = expected + "";
if (!numberSubstring.startsWith(expectedString)) {
// The next number was not found: the sequence is not an aggregated number
return false;
}

// Do recursion on the rest of the string
String newNumberSubstring = numberSubstring.substring(expectedString.length());
}
}``````

-------------------------------------------------

``````import static org.junit.Assert.*;

import org.junit.Test;

public class IsAggregatedNumberTest {
private AggregatedNumber numberChecker = new AggregatedNumber();

@Test
public void testFibSimple() {
boolean test = numberChecker.testNumber("112");
assertTrue(test);
}

@Test
public void testLengthTwo() {
boolean test = numberChecker.testNumber("11");
assertTrue(test);
}

@Test
public void testFibMediumPrependNine() {
boolean test = numberChecker.testNumber("911235813");
assertFalse(test);
}

@Test
public void testSkip() {
boolean test = numberChecker.testNumber("1012");
assertFalse(test);
}

@Test
public void testZero() {
boolean test = numberChecker.testNumber("000");
assertTrue(test);
}

@Test
public void testFibZeroes() {
boolean test = numberChecker.testNumber("00000000000");
assertTrue(test);
}

@Test
public void testZeroTwo() {
boolean test = numberChecker.testNumber("022461016264268110178");
assertTrue(test);
}

@Test
public void testZeroTwenty() {
boolean test = numberChecker.testNumber("02020406010016026042068011001780");
assertTrue(test);
}

@Test
public void testFibMedium() {
boolean test = numberChecker.testNumber("11235813");
assertTrue(test);
}

@Test
public void testFibWrong() {
boolean test = numberChecker.testNumber("113");
assertFalse(test);
}

@Test
public void testFibDoubleDigits() {
boolean test = numberChecker.testNumber("122436");
assertTrue(test);
}

@Test
public void testFibDoubleDigits2() {
boolean test = numberChecker.testNumber("1299111210");
assertTrue(test);
}

@Test
public void testFibTripleDigits() {
boolean test = numberChecker.testNumber("112112224");
assertTrue(test);
}

@Test
public void testFibSingleDoubleDigits() {
boolean test = numberChecker.testNumber("11011213253");
assertTrue(test);
}

@Test
public void testFibNonGreedy() {
boolean test = numberChecker.testNumber("1125126");
assertTrue(test);
}

@Test
public void testFibWrong2() {
boolean test = numberChecker.testNumber("11251265");
assertFalse(test);
}

@Test
public void testMediumInitials() {
boolean test = numberChecker.testNumber("100000100000200000");
assertTrue(test);
}

@Test
public void testFibLong() {
boolean test = numberChecker.testNumber("011235813213455891442333776109871597258441816765");
assertTrue(test);
}

@Test
public void testFibHuge() {
boolean test = numberChecker.testNumber("0112358132134558914423337761098715972584418167651094617711286574636875025121393196418317811");
assertTrue(test);
}

@Test
public void testGigangtic() {
boolean test = numberChecker.testNumber("011235813213455891442333776109871597258441816765109461771128657463687502512139319641831781151422983204013462692178309352457857028879227465149303522415781739088169632459861023341551655801412679142964334944377014087331134903170183631190329712150734807526976777874204912586269025203650110743295128009953316291173862675712721395838624452258514337173654352961625912867298799567220260411548008755920250473078196140527395378816557470319842106102098577231716768017756527777890035288449455702128537272346024814111766903046099419039249070913530806152117012949845401187926480651553304939313049695449286572111485077978050341645462290670755279397008847578944394323791464");
assertTrue(test);
}
}``````

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

``````enum XYZPhase {xx,yy,zz};

bool IsAggregatedNumberAux(
long long AggregatedX,
long long AggregatedY,
long long AggregatedZ,
XYZPhase Phase,
long long NumToCheck,
int AggregatedLength
)

{
AggregatedLength++;
if (NumToCheck==0) {
return false;
}
if (Phase==xx) {
if (AggregatedX + AggregatedY == AggregatedZ)
{
if (NumToCheck<10) { //we checked the last digit
return true;
}
AggregatedZ=AggregatedY;
AggregatedY=AggregatedX;
return (IsAggregatedNumberAux(
0,
AggregatedY,
AggregatedZ,
xx,
NumToCheck,
0
));
}
return (IsAggregatedNumberAux(
AggregatedX+(NumToCheck%10)*AggregatedLength,
AggregatedY,
AggregatedZ,
xx,
NumToCheck/10,
AggregatedLength
));
}
if (Phase==yy) {
if ((IsAggregatedNumberAux(
AggregatedX,
AggregatedY+(NumToCheck%10)*AggregatedLength,
AggregatedZ,
yy,
NumToCheck/10,
AggregatedLength
)))
{
return true;
}
return IsAggregatedNumberAux(
AggregatedX,
AggregatedY+(NumToCheck%10)*AggregatedLength,
AggregatedZ,
xx,
NumToCheck/10,
0
);
}

//phase == zz
if ((IsAggregatedNumberAux(
AggregatedX,
AggregatedY,
AggregatedZ+(NumToCheck%10)*AggregatedLength,
zz,
NumToCheck/10,
AggregatedLength
)))
{
return true;
}
return IsAggregatedNumberAux(
AggregatedX,
AggregatedY,
AggregatedZ+(NumToCheck%10)*AggregatedLength,
yy,
NumToCheck/10,
0
);
}

bool IsAggregatedNumber(long long NumToCheck)
{
return (IsAggregatedNumberAux(
0,
0,
0,
zz,
NumToCheck,
0
));
}``````

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

``````public static boolean isAggregatedNumberSequence(String numberSequenceStr) {
int isize = 1;
for(int i = 0; i + isize < numberSequenceStr.length(); isize++) {
int jsize = 1;
for(int j = i + isize; j + jsize < numberSequenceStr.length(); jsize++) {
int inti = Integer.parseInt(numberSequenceStr.substring(i, i + isize));
int intj = Integer.parseInt(numberSequenceStr.substring(j, j + jsize));
if (isAggregateNumber(inti, intj, numberSequenceStr.substring(j + jsize, numberSequenceStr.length()))) {
return true;
}
}
}
return false;
}

private static boolean isAggregateNumber(int prev, int current, String str) {
if(str.length() == 0) {
return true;
}
int next = prev + current;
if(str.startsWith(next + "")) {
return isAggregateNumber(current, next, str.replaceFirst(next + "", ""));
}
return false;
}

public static void main(String[] args) {
System.out.println(isAggregatedNumberSequence("123"));
System.out.println(isAggregatedNumberSequence("11111111112"));
System.out.println(isAggregatedNumberSequence("000"));
System.out.println(isAggregatedNumberSequence("11235813"));
System.out.println(isAggregatedNumberSequence("112112224"));
System.out.println(isAggregatedNumberSequence("124"));

}``````

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

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

I think that we can identify whether the number can be decompose into 3 numbers a,b,c such that a+b = c first. And then if any subset of the number can be decomposed, we then propagate to the end of the number. It will take O(n^3)

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

A working solution in ruby. Like many people comment in here, the key is to get the first 2 elements. Given that, you just need to perform checks on the remaining elements. It requires a lot of switching between integers and strings.

``````# Gets the size of the biggest chunk of numbers you can take
# and iterates from 1 to that, taking the first 2 numbers
# and performing the check with that
def aggregated_check(number)
biggest_chunk_size = number.to_s.split('').count/3
return false if biggest_chunk_size < 1

1.upto(biggest_chunk_size) do |chunk_size|
split_number = spaces_on(number, chunk_size)

next unless split_number.select { |number| number.size != chunk_size }.empty?

return true if is_aggregate?(split_number)
end

false
end

# Returns an array with the number divided in X intervals
def spaces_on(number, interval)
number.to_s.gsub(/.{#{interval}}/, '\& ').split
end

# Takes first and second numbers and adds them, saves the result in "sum"
# then takes "sum.digits" characters from the string, if that is different to sum
# just returns false. If its true, then first becomes second, second becomes sum.
def is_aggregate?(split_number)
first = split_number.shift.to_i
second = split_number.shift.to_i
number = split_number.join

loop do
sum            = first + second
sum_digits     = sum.to_s.size
return true if number[sum_digits - 1].nil?
possible_match = number[0..sum_digits - 1].to_i
return false if sum != possible_match

number = number[sum_digits..number.size]
first  = second
second = sum
end

end``````

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

The working code is here

int main(void) {

char Str[]="112112224";
AgreegatedFunction(Str);
}
void AgreegatedFunction(char *inputstr)
{

int NoofDigits = 1,resultdigits;
int stridx=0;
char operand[10],val[10];
int operand1,operand2;
int i,result;
int valid= 0;
while(*(inputstr+stridx) != '\0')
{
// get operand 1
if(!valid)
{
for( i=0;i<NoofDigits && *(inputstr+stridx) != '\0';i++, stridx++)
operand[i]=*(inputstr+stridx);

operand[i]='\0';
operand1 = atoi(operand);

// get operand 2
for( i=0;i<NoofDigits && *(inputstr+stridx) != '\0';i++, stridx++)
operand[i]=*(inputstr+stridx);

operand[i]='\0';
operand2 = atoi(operand);
}

resultdigits = Noofdigitsforresult(operand1+operand2);
// get result
for( i=0;i< resultdigits && *(inputstr+stridx) != '\0';i++, stridx++)
val[i]=*(inputstr+stridx);

val[i]='\0';
result = atoi(val);

if((operand1 + operand2) != result )
{
NoofDigits++;
valid = 0;
if( stridx < strlen(inputstr))
{
stridx = 0;
}
}
else
{
printf("operand one %d operand two %d result %d\n",operand1,operand2,result);
valid = 1;
operand1 = operand2;
operand2 = result;

}

}
if(valid)
printf(" it is a aggregated number");
else
printf(" it is not a aggregated number");
}

int Noofdigitsforresult(int result)
{
int noofdigits = 1;

while(result > 9)
{
result = result /10;
noofdigits++;
}
printf("No.of digits %d",noofdigits);
return noofdigits;
}

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

``````def get_digits(n):
if n == 0:
return [0]
digits = []
while n > 0:
digits.insert(0, n % 10)
n = n // 10
return digits

def make_number(digits):
n = 0
for digit in digits:
n *= 10
n += digit
return n

def get_aggregates(n):
"""Get the aggregate factoring of n, that is split n into
a list of numbers so that each number is the sum of two previous ones,
and all numbers concatted together form n. Return empty list if no such
grouping exists.

>>> get_aggregates(112358)
[1, 1, 2, 3, 5, 8]
>>> get_aggregates(122436)
[12, 24, 36]
>>> get_aggregates(1299111210)
[12, 99, 111, 210]
>>> get_aggregates(112112224)
[112, 112, 224]

The elements don't have to be nondecreasing:
>>> get_aggregates(10112)
[1, 0, 1, 1, 2]
>>> get_aggregates(1211314)
[12, 1, 13, 14]
>>> get_aggregates(12112133)
[121, 12, 133]

The list must be at least 3 members long:
>>> get_aggregates(1)
[]
>>> get_aggregates(137)
[]
>>> get_aggregates(1125)
[]
"""

def make_aggregate(first, second, rest):
aggregate = [first, second]
prev = first
cur = second

while len(rest) > 0:
nextt = prev + cur
digits = get_digits(nextt)
if rest[:len(digits)] == digits:
aggregate.append(nextt)
prev = cur
cur = nextt
rest = rest[len(digits):]
else:
return None
return aggregate

digits = get_digits(n)
for first_length in range(1, len(digits)):
for second_length in range(first_length + 1, len(digits)):
first = make_number(digits[:first_length])
second = make_number(digits[first_length:second_length])
rest = digits[second_length:]
aggr = make_aggregate(first, second, rest)
if aggr:
return aggr
return []

def is_aggregate(n):
return get_aggregates(n) is not None

if __name__ == "__main__":
import doctest
doctest.testmod()``````

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

We figure out first and second numbers, build aggregated number, and check if it is the given number. If it is not, take another digit to rebuild second number and repeat the process. This needs to continue for first number too if the built aggregated number is not the given one. Worst Case Scenario [for example 1123581323] : O(N^3) and Best Case Scenario [for example 1123581321]: O(N)

``````public boolean isAggregate(int input) {
String s = String.valueOf(input);
if (s.length() < 3) {
return false;
}
for (int i = 1; i <= s.length() - 2; i++) {
for (int j = 1; i + j <= s.length() - 1; j++) {
int number1 = Integer.parseInt(s.substring(0, i));
int number2 = Integer.parseInt(s.substring(i, i + j));
int number3 = number1 + number2;
int num2Size = String.valueOf(number2).length();
int num3Size = String.valueOf(number3).length();
double d1 = Math.pow(10, num2Size + num3Size) * number1;
double d2 = Math.pow(10, num3Size) * number2;
double d3 = number3;
int result = (int) (d1 + d2 + d3);
while (String.valueOf(result).length() < s.length()) {
int temp = number2 + number3;
int size = String.valueOf(temp).length();
double dd1 = Math.pow(10, size) * result;
if (dd1 > Integer.MAX_VALUE) {
break;
}
result = (int) (dd1 + temp);
number2 = number3;
number3 = temp;
}
if (result == input) {
return true;
}
}
}
return false;
}``````

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

For each possible pair of start numbers validate if the number string is same is sequence created by using them as seed values. If any such pair is found then true else false.

``````static bool CheckIfAggregate(string num)
{
int index1 = 0;
int index2 = 1;

while (index1 < num.Length-2)
{
index2 = index1+1;
var num1 = int.Parse(num.Substring(0, index1+1));
while(index2 < num.Length-1)
{
var num2 = int.Parse(num.Substring(index1+1, index2-index1));
if(IsSequencePresent(num.Substring(index2+1), num1, num2))
{
return true;
}
index2++;
}
index1++;
}
return false;
}

static bool IsSequencePresent(string num, int num1, int num2)
{
if (String.IsNullOrEmpty(num))
{
return false;
}

while (String.IsNullOrEmpty(num) == false)
{
if (!num.StartsWith((num1 + num2).ToString()))
{
return false;
}
var temp = num1+num2;
num1 = num2;
num2 = temp;
num = num.Substring(temp.ToString().Length);
}

return true;
}``````

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

Something like this. Idea is to scan from right to left. First look for the right most digit to see if it is sum of any two numbers on the left. if it is, recursively do the same thing for the rest of the number on left. if it also returns true then it's aggregated. if the recursive call returns false, then you look for the right most two digits and recursive again.. you do it until n/2 digits on the right, if you can't find it, return false.
there are two recursive calls one dividing the number to left and right parts and second one is to look for the permutations of n*2 digits to see if any of permutations' sum gives the summation for the right most n digits..

``````#include<vector>
#include <iostream>
using namespace std;

bool isAggregated(int number);

void parseArrayForTwoValues(std::vector<int>& arr, int index, int& left, int& right)
{
left = 0;
right = 0;
int current = 0;
int base = 1;
while(current < index)
{
left *= base;
base *= 10;
current ++;
}

base =1;
while(current < (int)arr.size())
{
right *= base;
base *=10;
current ++;
}
}

bool sumExists(int searchForValue ,std::vector<int> arr, int index)
{
if (index == arr.size())
return false;

for (int i = 0; i < arr.size(); i++)
{
int left = 0, right = 0;
parseArrayForTwoValues(arr, index, left, right);
if ((left + right ) == searchForValue)
return true;
if( sumExists(searchForValue, arr, index+1))
return true;
arr.erase(arr.begin());
if (sumExists(searchForValue, arr, 1))
return true;
}
}

int digitLength(int number)
{
int size = 0;
if (!number) return 1;
while(number)
{
number /=10;
size++;
}
return size;
}

int extractSubnumberOnRight(int number, int skipFromRight, int numDigits)
{
while (skipFromRight != 0)
{
// reduce the number
number /= 10;
skipFromRight--;
}
if (numDigits == -1)
return number;
int mod = 10;
while(numDigits > 1)
{
mod *= 10;
numDigits--;
}
return number % mod;
}

std::vector<int> numberToArray(int number)
{
std::vector<int> result;
if (!number)
{
result.push_back(0);
return result;
}
while(number)
{
int val = number%10;
result.insert(result.begin(), val);
number/=10;
}
return result;
}

bool isAggregatedHelper(int number, int numOfDigitsToCheckOnRight)
{
if (numOfDigitsToCheckOnRight > digitLength(number)/2)
return false;

int lookForSum = extractSubnumberOnRight(number, 0, numOfDigitsToCheckOnRight);
int lookIn     = extractSubnumberOnRight(number, numOfDigitsToCheckOnRight, 2* numOfDigitsToCheckOnRight);
int restOfNumber = extractSubnumberOnRight(number, numOfDigitsToCheckOnRight*3, -1);

std::vector<int> arr = numberToArray(lookIn);
bool sumFound = sumExists(lookForSum, arr, 1);
if (sumFound)
{
if (digitLength(lookForSum)+digitLength(lookIn) == digitLength(number))
return true;
if (isAggregated(restOfNumber))
return true;
}
return isAggregatedHelper(number, numOfDigitsToCheckOnRight+1);
}

bool isAggregated(int number)
{
return isAggregatedHelper(number, 1);
}

int _tmain(int argc, _TCHAR* argv[])
{
bool result = isAggregated(112112224);
cout << result << endl;
return 0;
}``````

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

``````bool is_aggnum(int num)
{
char s[256];
char tmp1[256], tmp2[256], tmp3[256];
snprintf(s, 256, "%d", num);

size_t len = strlen(s);
for (int i = 1; i < (len+1)/2; i++) {
strncpy(tmp1, s, i);
tmp1[i] = 0;
int a = atoi(tmp1);
for (int j = 1; j < (len+1)/2; j++) {
strncpy(tmp2, s+i, j);
tmp2[j] = 0;
int b = atoi(tmp2);
int c = a + b;

snprintf(tmp3, 256, "%d", c);
int x = strlen(tmp3);
//printf("%s %s %s\n", tmp1, tmp2, tmp3);
if (strncmp(s+i+j, tmp3, x) == 0) {
if (len == i + j + x)
return true;
if (is_aggnum(atoi(s+i)))
return true;
}
}
}
return false;
}``````

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

/*********************************************************************
* we will name a number "aggregated number" if this number has the following
* attribute: just like the Fibonacci numbers 1,1,2,3,5,8,13.....
*
* the digits in the number can divided into several parts, and the later part
* is the sum of the former parts.
*
* like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8 122436, because 12+24=36
* 1299111210, because 12+99=111, 99+111=210 112112224, because 112+112=224 so
* can you provide a function to check whether this number is aggregated number
* or not?
*
*********************************************************************/

``````public class AggregatedNumberProblem {

public boolean isAggregated(int number){
String str = String.valueOf(number);
boolean status = false;
for(int length1=1;length1 < ((str.length()/2)+1);length1++){
for(int length2=1;length2<=((str.length()/2)+1);length2++){
System.out.println("first"+str.substring(0,length1));
System.out.println("second"+str.substring(length1,length1+length2));
System.out.println("rest"+str.substring(length1+length2));
if( isMatch(str.substring(0,length1),str.substring(length1,length1+length2),str.substring(length1+length2))==true){
status = true;
}
}
}
System.out.println("status is"+status);

return status;
}

public boolean isMatch(String str1,String str2,String str3){
if(str3.equals("")){return true;}
System.out.println("first"+str1);
System.out.println("second"+str2);
System.out.println("rest"+str3);
int a = Integer.parseInt(str1);
int b = Integer.parseInt(str2);
int c = a+b;
String temp = String.valueOf(c);
if(temp.length() > str3.length()){
return false;
}
String third = str3.substring(0,temp.length());
int match = Integer.parseInt(third);
if(match == a+b){
return isMatch(str2,third,str3.substring(third.length()));
}
return false;
}

public static void main(String args[]){
AggregatedNumberProblem anp = new AggregatedNumberProblem();
anp.isAggregated(12113);
}
}``````

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

I write a code in Java and pass all the cases appeared in this post. Let me know if it has any problem:

public boolean ST(String s){
for(int first = 1; first <= s.length()/2; first++){
for(int second = first+1; second <= (s.length()-first)/2 + first; second++){
if(CK(s.substring(0,first), s.substring(first, second), s.substring(second))){
return true;
}
}
}
return false;
}

public boolean CK(String s1, String s2, String rest){
int i1 = Integer.parseInt(s1);
int i2 = Integer.parseInt(s2);
String sum = (i1 + i2) + "";
if(sum.length() > rest.length()){
return false;
}
if(sum.equalsIgnoreCase(rest.substring(0, sum.length()))){
if(sum.length() == rest.length()){
return true;
}
return CK(s2, sum, rest.substring(sum.length()));
}
return false;
}

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

122122244112
122+122=244 and 1+1=2 does not pass.

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

``````public static bool IsAgggregated(string num)
{
if (num.Length < 3)
return false;

//We just need to find out if the string is an aggregate for all combinations of first 2 numbers
for (int i = 0; i <= num.Length - 3; i++)
{
string numA = num.Substring(0, i + 1);
for (int j = i + 1; j <= num.Length - 2; j++)
{
string numB = num.Substring(i+1, j-i);
if(AggTest(numA, numB, num.Substring(numA.Length + numB.Length)))
return true;
}
}
return false;
}
public static bool AggTest(string a, string b, string number)
{
int numA = int.Parse(a);
int numB = int.Parse(b);
int sum = numA + numB;

if(sum == int.Parse(number))
return true;

if(number.StartsWith(sum.ToString()))
{
return AggTest(numB.ToString(), sum.ToString(), number.Substring(sum.ToString().Length));
}

return false;
}``````

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

Here is a working python solution using Shawn's logic:

``````def find_aggregated_number(A):
for i in range(1,int(len(A)/2)):
for j in range(i+1,int(len(A)*2/3)+1):
if(check_aggregate(i,j,A)):
return True
return False

def check_aggregate(i,j,A):
result = A[0:i] + A[i:j]
first = int(A[0:i])
second = int(A[i:j])

while(len(A) > len(result)):
third = first + second
result = result + str(third)
first = second
second = third
return (len(result)==len(A)) and (result == A)

for A in ["112358","122436","1299111210","112112224"]:
if (find_aggregated_number(A)):
print("{} is an aggregated number".format(A))
else:
print("{} is not an aggregated number".format(A))``````

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

``````def is_aggregated(number):
num = str(number)

for i in range(1, len(num) - 1):
summand1 = int(num[:i])

for j in range(i + 1, len(num)):
summand2 = int(num[i:j])
sum = summand1 + summand2;
pos = j

while num.startswith(str(sum), pos):
pos += len(str(sum))
summand1, summand2 = summand2, sum
sum = summand1 + summand2

if pos == len(num):
return True

return False``````

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

``````public static boolean isAggregatedNumber(int n){
boolean result = false;
String num = (n+"");
int len = num.length();
if(len<2){return true;}
int x, y;
for(int i=1; i<len; i++){
for(int j=i+1; j<len; j++){
x = Integer.parseInt(num.substring(0,i));
y = Integer.parseInt(num.substring(i,j));
int s = x+y; String ss = (s+"");
if(j+ss.length()<=len && ss.equalsIgnoreCase(num.substring(j, j+ss.length()))){
if(j+ss.length()==len) return true;
return isAggregatedNumber(Integer.parseInt(num.substring(i)));
}
}
}
return result;
}``````

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

your code works fine for most numbers but fails for numbers like 112233 because you did not handle the logic for the cases where the first three digits agree the requirement and the rest dosenot but the number as a whole does...
how ever i modified your code to make it work let me know if there are any special cases that the following code wont work for.....

``````package interviews;

public class AggNum {
public boolean isAggregatedNumber(int n){
boolean result = false;
String num = (n+"");
int len = num.length();
if(len<2){return true;}
int x, y;
int length=1;
for(int i=length; i<len; i++){

for(int j=i+length; j<len; j++){
x = Integer.parseInt(num.substring(0,i));
y = Integer.parseInt(num.substring(i,j));
int s = x+y; String ss = (s+"");
System.out.println("num = "+num+" i = "+i+" j = "+j+" x = "+x+" y = "+y+" s = "+s);

if(j+ss.length()<=len && ss.equalsIgnoreCase(num.substring(j, j+ss.length()))){
if(j+ss.length()==len) return true;
if(isAggregatedNumber(Integer.parseInt(num.substring(i))))
{
return true;
}
else
{
length++;
}
}
}
}
return result;
}

public static void main(String[] args) {
int n = 114228342;

AggNum a = new AggNum();
System.out.print(a.isAggregatedNumber(n));

}

}``````

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

hi rajesh,
nice logic but it may fail for the this case
10111 -> 10+1->11

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.