trjhtr

If we are given an integer $textSumofSubSums(N)$, and number of digits $D$ that $N$ has, we are asked to find the original integer $ N $.

Example:
If we are given $2148$ , and $D = 4$.
We need to find $1935$ , because
$$2148 = 1935 + frac193510+frac1935100+frac19351000$$

Now I have a code which solves the task but it takes a lot of time to do so...

#include <iostream> 
#include <cmath>
using namespace std;

 long long int Sum_of_Sub_Sums(long long int a) 
 long long int Sum = 0;
 for (a = a; a > 0; a /= 10) 
 Sum += a;
 
 return Sum; 
 

 int main() 
 long long int maxSum[15] = 9, 108, 1107, 11106, 111105, 1111104, 11111103, 111111102, 1111111101, 11111111100, 111111111099, 1111111111098, 11111111111097, 111111111111096, 1111111111111095 ;
 long long int number;
 int numDigits;
 cin >> number >> numDigits;
 if (number < 10 && numDigits < 2) 
 cout << number;
 
 else 
 long long int l = pow(10,numDigits-1);
 long long int r = maxSum[numDigits-1];
 long long int mid= l + (r-l)/2;
 while(Sum_of_Sub_Sums(mid)!= number)
 if(Sum_of_Sub_Sums(mid) > number)
 r = mid;
 
 else 
 l = mid;
 
 mid = l + (r-l)/2;
 
 cout<<fixed<<mid;
 
 return 0;
 

how can I decrease the complexity of my code ?

$EDIT: $
If anyone is interested here is the working solution

#include <iostream>
#include <cmath>
using namespace std;

long long int Sum_of_Sub_Sums(long long int a) 
 long long int Sum = 0;
 for (a = a; a > 0; a /= 10) 
 Sum += a;
 
 return Sum;


int main() 
 long long int number;
 long double tmp;
 int numDigits;
 cin >>number >>numDigits;
 if (number < 10 && numDigits < 2) 
 cout << number;
 else 
 tmp=(pow(10,numDigits)-1)/(9*pow(10,numDigits-1));
 long long int current = number/tmp;
 while (Sum_of_Sub_Sums (current) != number) 
 if (Sum_of_Sub_Sums (current) > number) 
 current--;
 else 
 current++;
 
 Sum_of_Sub_Sums (current);
 
 cout << fixed << current;
 
 return 0;

It seems to me that you could find an approximate solution easily.
Maybe you could then use this knowledge to iterate through less numbers.

When checking your number, you do this operation for D = 4: a + truncate(a/10) + truncate(a/100) + truncate(a/1000), which can be quite close to the float a + a/10 + a/100 + a/1000, but not exactly the same value as any of the terms might not be an integer value.

Basically, the float computation is a * 1.111, and the result is probably not too far from your number N.

If you take N / 1.111, that should bring you pretty close to your desired number. In your example, 2148 / 1.111 = 1933.39.

You also know that the float value that you find with this division is lower than the one you want, because of truncations.

A naive way would be to start from this value, and iterate until you find a solution. I am not sure how well this would be compared to your binary search, but this could already be something worth trying.

EDIT

Just another thought: you can also take into account that the sum of digits must match the last digit of N during your iteration (1 + 9 + 3 + 5) % 10 = 8 = 2148 % 10, this will help iterate only 9 by 9 instead of 1 by 1.