Find a number K having sum of numbers obtained by repeated removal of last digit of K is N

Given an integer N, the task is to find an integer K such that the sum of the numbers formed by repeated removal of last digit of K is equal to N.

Examples:

Input: N = 136

Output: 123

Explanation:

Click to enlarge

The numbers formed by repeatedly removing the last digit of 123 are {123, 12, 1}.

Therefore, the sum of these numbers = 123 + 12 + 1 = 136( = N).

Input: N = 107

Output: 98

Explanation:

The numbers formed by repeatedly removing the last digit of 98 are {98, 9}.

Therefore, the sum of these numbers = 98 + 7 = 107( = N).

Approach: The approach is based on the following observations:

Consider K = 123.

The possible numbers formed from 123 are 1, 12, and 123.

Now, 123 can be expressed as 100 + 20 + 3. If all the other numbers are expressed similarly, then the idea is to know the position and frequency of each digit in all the numbers combined, to get the total sum as N.

Digit Frequency of each digit Sum

units tens hundreds

1 1 1 1 1*1 + 1*10 + 1*100 = 111

2 1 1 2*1 + 2*10 = 22

3 1 3*1 = 3

Now, for the given number N of length L. Divide the number with L number of 1s to get the highest place digit.

Calculate the remainder which will be our newly formed N.

Again divide the newly formed N with (L – 1) number of 1s to get 2nd highest place digit and continue till the L becomes 0.

Follow the steps below to solve the problem:

Let L be the count of digits in the given number N.

Initialize a string str as L numbers of 1s in it.

Initialize a variable ans as zero that will store the resultant number K.

Iterate until the string str is not empty and follow the steps below:

Convert the string str to number using the function stoi() and store it in M.

Divide N by M and update ans as:

ans = ans*10 + (N/M)

Update N to N % M.

Remove the last character from the string str.

After the above steps, print the value stored in the ans which is the required value of K.

Below is the implementation of the above approach:

// C++ program for the above approach 

  

#include <bits/stdc++.h> 

using namespace std; 

  

// Function to find the value of K 

int findK(int N, int l) 

{ 

    // Stores l number of 1s 

    string ones = ""; 

  

    while (l--) { 

  

        // Storing 1's 

        ones = ones + '1'; 

    } 

  

    // Stores the value of K 

    int ans = 0; 

  

    // Iterate until ones is empty 

    while (ones != "") { 

  

        // Convert ones to number 

        int m = stoi(ones); 

  

        // Update the ans 

        ans = (ans * 10) + (N / m); 

  

        // Update N to N%m 

        N = N % m; 

  

        // Removing last digit from ones 

        ones.pop_back(); 

    } 

  

    // Return the value of K 

    return ans; 

} 

  

// Driver Code 

int main() 

{ 

    // Given number N 

    int N = 136; 

  

    // Number of digits in N 

    int L = to_string(N).length(); 

  

    // Funtion Call 

    cout << findK(N, L); 

  

    return 0; 

} 

Output:

123

Time Complexity: O(log10N)

Auxiliary Space: O(1)