Given **N **coins, the sequence of numbers consists of** {1, 2, 3, 4, ……..}.** The cost for choosing a number in a sequence is the number of digits it contains. **(For example **cost of choosing 2 is **1 **and for 999 is **3), **the task is to print the **Maximum **number of elements a sequence can contain.

Any element from

{1, 2, 3, 4, ……..}. can be used at most 1 time.

**Examples: **

Input:N = 11Output:10Explanation:ForN = 11-> selecting 1 with cost 1, 2 with cost 1, 3 with cost 1, 4 with cost 1, 5 with cost 1, 6 with cost 1, 7 with cost 1, 8 with cost 1, 9 with cost 1, 10 with cost 2.

totalCost = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 11.

Input:N = 189Output:99

**Naive approach: **The basic way to solve the problem is as follows:

Iterateifrom 1 to infinity and calculate the cost for currentiif the cost foriis more than the number of coins which isNtheni – 1will be the answer.

**Time Complexity: **O(N * logN)**Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can be optimized based on the following idea:

This Problem can be solved usingBinary Search. A number of digits with given cost is a monotonic function of type T T T T T F F F F. Last time the function was true will generate an answer for the Maximum length of the sequence.

Follow the steps below to solve the problem:

- If the cost required for digits from
**1**to**mid**is less than equal to**N**update**low**with**mid**. - Else
**high**with**mid – 1**by ignoring the right part of the search space. - For printing answers after binary search check whether the number of digits from
**1**to**high is**less than or equal to**N**if this is true print**high** - Then check whether the number of digits from
**1**to**low**is less than or equal to**N**if this is true print**low**. - Finally, if nothing gets printed from above print 0 since the length of the sequence will be 0.

Below is the implementation of the above approach:

## C++

// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to count total number // of digits from numbers 1 to N int totalDigits(int N) { int cnt = 0LL; for (int i = 1; i <= N; i *= 10) cnt += (N - i + 1); return cnt; } // Function to find Maximum length of // Sequence that can be formed from cost // N void findMaximumLength(int N) { int low = 1, high = 1e9; while (high - low > 1) { int mid = low + (high - low) / 2; // Check if cost for number of digits // from 1 to N is less than equal to N if (totalDigits(mid) <= N) { // atleast mid will be the answer low = mid; } else { // igonre right search space high = mid - 1; } } // Check if high can be the answer if (totalDigits(high) <= N) cout << high << endl; // else low can be the answer else if (totalDigits(low) <= N) cout << low << endl; // else answer will be zero. else cout << 0 << endl; } // Driver Code int main() { int N = 11; // Function Call findMaximumLength(N); int N1 = 189; // Function call findMaximumLength(N1); return 0; }

**Time Complexity: **O(logN^{2}) (first logN is for logN operations of binary search, the second logN is for finding the number of digits from 1 to N)**Auxiliary Space: **O(1)

**Related Articles: **