CareerCup

I wrote such a dynamic programming implementation:

int sum_subs(const string& s)
{
    cout << "(" << s << ") ";
    
    const auto len = s.length();

    if(len == 0)
    {
        return 0;
    }

    int sum = 0;

    for_each(s.begin(), s.end(), [&sum](char c) { sum *= 10; sum += (c - '0'); });

    return sum + sum_subs(s.substr(0, len-1)) + sum_subs(s.substr(1, len-1));
}

But when I tested it later I realized that it does not avoid duplicate substring. For example, for "123" it processes the following substrings: 123 12 1 2 23 2 3. As we can see, substring '2' appears twice. Is there a way to fix this algorithm to avoid duplicates without storing all possible substrings in a set?

1. Permute the string and all it's substrings into a list
2. atoi each string in the output list and sum the result

int sum(Sting str){
int sum = 0;

for(int i=str.length()-1; i>=0; i--){
for(int j=i, k=0; i<=str.length()-1; j++,k++){
sum += Integer.parseInt(str.substring(k,j+1));
}
}

return sum;
}

Javascript:

function solution(str){
    var sum = 0;
    for(var i=0; i<str.length; i++){
        for(var j=1; i+j<=str.length; j++){
            sum += parseInt(str.substr(i, j));
        }
    }
    return sum;
}

Who will tell me which complexity is there?

And btw, for "123" correct answer is '164'..

Note: parseInt can be avoided if we'll remember digits of inner loop.

C Code:

long sum_subs(int n, char* dgtstr) {
        long sum = 0;
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < n - i; j++)
                        sum += (dgtstr[i] - '0') * pow(10, j) * (i + 1);
        }
        return sum;
}

Test Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char** argv) {
        int N = 3;
        if(argc > 1)
                N = atoi(argv[1]);
        char* dgtstr = malloc(N + 1);
        printf("N: %d\n", N);
        for(int i = 0; i < N; i++)
                dgtstr[i] = '0' + (i + 1)%10;
        dgtstr[N] = 0;
        printf("%s: %ld\n", dgtstr, sum_subs(N, dgtstr));
        return 0;
}

//considering only positive numbers
    private static long sum(String n){
        if(n == null || n.trim().length == 0)
            return 0;
        n = n.trim();
    	int length = n.length();
    	long sum = 0;
    	for(int i=1; i<= length; i++){
    		for(int j =0; j+i<=length; ++j){
    		   System.out.println(n.substring(j,j+i));
    			sum += Integer.parseInt(n.substring(j,j+i));
    		}
    	}
    	return sum;
    }

We play a few tricks to get the time complexity down to O(n) and the space complexity down to O(1), where n is the length of the string.

long long int
mySum(const std::string & input)
{
  const auto len = input.size();
  long long result = 0;
  int sumOfPowersOfTen = 1;
  //sumOfPowersOfTen will hold the value of
  // \sum_{j=1}_{n-1-i} 10^i

  for(int i = len-1; i >= 0; --i){
    long long term = (long long) input.at(i) - (long long) '0';    
    term *= (i+1);
    term *= sumOfPowersOfTen;    
    sumOfPowersOfTen *= 10;
    ++sumOfPowersOfTen;    
    result += term;    
  }
  return result;
}

#include<iostream>
#include<string>
#include<set>
#include<algorithm>
#include <functional>
#include <numeric>

using namespace std;

int sum(string &str)
{
set<int> myset;
int number = 0;
for (int i = 0; i < str.size(); i++)
{
string ss = "";

for (int j = i; j < str.size(); j++)
{
ss = ss + str[j];
number = stoi(ss);
myset.insert(number);
}
}

static int count = accumulate(myset.begin(), myset.end(), 0);

return count;
}
int main()
{
string str = "123";

cout << sum(str) << endl;

return 0;
}

set<int> myset;
int number = 0;
for (int i = 0; i < str.size(); i++)
{
string ss = "";

for (int j = i; j < str.size(); j++)
{
ss = ss + str[j];
number = stoi(ss);
myset.insert(number);
}
}

static int count = accumulate(myset.begin(), myset.end(), 0);

return count;

set<int> myset;
int number = 0;
for (int i = 0; i < str.size(); i++)
{
string ss = "";
for (int j = i; j < str.size(); j++)
{
ss = ss + str[j];
number = stoi(ss);
myset.insert(number);
}
}
static int count = accumulate(myset.begin(), myset.end(), 0);
return count;

set<int> myset;
	int number = 0;
	for (int i = 0; i < str.size(); i++)
	{
		string ss = "";

		for (int j = i; j < str.size(); j++)
		{
			ss = ss + str[j];
			number = stoi(ss);
			myset.insert(number);
		}		
	}

	static int count = accumulate(myset.begin(), myset.end(), 0);

	return count;