Additive Sequence Algorithm

Question

I am practicing algorithms for interviews and came across this question on Career Cup and SO An additive sequence number is which when splitted in two different number forms additive seq.

Ex: 1235 (split it 1,2,3,5) Ex: 12122436(split 12,12,24,36) given a range find all additive seq numbers ?

Below is what I tried, I know it is not efficient and not sure about its complexity. Also, It does not find numbers like 53811 and 12122436 which I am interested in finding. I will be really thankful if someone can guide me in right directions or come up with something more simple and efficient. Thanks!

#include <stdio.h>

void check_two_num_sum(int,int);
void check_sum(int);
int flag = 0;

int main(){

int high,low;
printf("Enter higher range\n");
scanf("%d",&high);
printf("Enter lower range\n");
scanf("%d",&low);
check_two_num_sum(high,low);

return 0;
}

void check_two_num_sum(int high, int low)
{
  flag=0;
  for(low;low<high;low++)
  {
    check_sum(low);  
    if(flag==1)
    {
       printf("this value has additive sequence %d \n",low);
       flag = 0; 
     }
  }
}

void check_sum(int input)
{
   int count = 1;
   int capture, result, temp_res=0, n=0;

   if(n==0){
    result = input%10;
        n++;
        input = input/10;
        capture = input;
    }

   while(input!=0)
   {
     temp_res = temp_res + input%10;    

     if(count ==2)
      {
         if(result == temp_res)
          { 
         if(capture < 100)
        {       flag = 1;
                    break; 
        }

         else{
              check_sum(capture);
        }
           }

          else {
          break;
        }
        } 
    count++;
    input = input/10;
  }
}

Hostetter

The first answer on the Career Cup website that you linked seems a good starting point. Are you using that trick in your code? – Illegitimate

Any number can be split into an additive seq, since a sequence may have one or two members as well. for example the number 696 can be split into: {6,9,6} which is not an additive seq, but can also be split into {69,6} or {6,96} or {696} which are addictive sequences. – Undersized

@AbhishekBansal i tried but i did not understand what he meant to say by "the digit numbers of T(1) and T(2) cannot be larger than half of that of max range " – Hostetter

Answer 1

I'm not sure how efficient it would be, but I might try something recursive.

For example, 53811

Point to the end of the string, say.

Var2 = 1
Var1 = 1

Check if Var0 equals Var2 - Var1

1 - 1 does not equal 8, so this strand of the function is terminated.

In the next strand of the function, Var2 equals the last two digits, 11; Var1 = 8

Check if Var0 equals Var2 - Var1

11 - 8 equals 3 so this strand of the function continues: Var2 = 8; Var1 = 3

Check if Var0 equals Var2 - Var1

8 - 3 equals 5 and this is also the end of the string so the function returns True

The base case seems to be if the pointer is at the beginning of the string or no viable variables could be tested. At each junction point, Var2 and Var1 would be altered accordingly to start a new strand; Var0 is deduced from the other two.

Stowell

I really like your idea and will definitely give it try. Thanks +1. – Hostetter

What is the difference between enumerating from the end versus from the begin? – Premonitory

@Premonitory I haven't given that choice too much thought; I just chose one to try and work out an example. – Wastage

Answer 2

Suppose the length of the original sequence is n. An obvious approach that can work is to brute forcely enumerate the length of the first and the second element, and check whether it is correct in linear time. Such an approach takes O(n ^ 3) time.

You claim that your approach takes O(n) time, but from your implementation, I suspect whether your n denotes the length of the original sequence.

Premonitory

I see what you are saying, I removed the claim saying O(n) complexity. Thanks! @Premonitory – Hostetter