8
\$\begingroup\$

If we are given an integer \$\text{SumofSubSums}(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 + \frac{1935}{10}+\frac{1935}{100}+\frac{1935}{1000}$$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ To post verbatim code in your question, just paste, select all lines and press CTRL-K. All it needs is indentation by four ' ' blank characters. \$\endgroup\$ Apr 7 '18 at 18:47
  • \$\begingroup\$ First of all , thank you very much ! I'm new here so forgive me haha, I tried CTRL+K and in between pasting the code but that didn't seem to work very well. \$\endgroup\$
    – Noodle
    Apr 7 '18 at 18:50
  • 1
    \$\begingroup\$ It seems like this can be solved in constant time ... Rounding might skew results a little bit though. \$\endgroup\$ Apr 7 '18 at 19:31
  • 2
    \$\begingroup\$ Yes @Incomputable, I was thinking the same. Something like, divide the number by 1.111... (how ever many digits), and increment until you have your number. \$\endgroup\$ Apr 7 '18 at 19:33
  • 1
    \$\begingroup\$ @JosephWood, on bigger examples rounding might destroy our solution :) darn integer division. Search could be done in vicinity of that result though, and a lot of computations could be reused. \$\endgroup\$ Apr 7 '18 at 19:34
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much ! Your idea was great , and contributed to my final solution , originally I had trouble because I was asked to find such a number in [0,10^15] in less than 3 seconds , finally I implemented the solution and is working for all test cases :) \$\endgroup\$
    – Noodle
    Apr 7 '18 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.