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 = 11
Output: 10
Explanation: For N = 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 = 189
Output: 99
Naive approach: The basic way to solve the problem is as follows:
Iterate i from 1 to infinity and calculate the cost for current i if the cost for i is more than the number of coins which is N then i – 1 will 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 using Binary 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 Nint 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// Nvoid 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 { // ignore 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 Codeint main(){ int N = 11; // Function Call findMaximumLength(N); int N1 = 189; // Function call findMaximumLength(N1); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to count total number of digits from numbers // 1 to N static int totalDigits(int N) { int cnt = 0; 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 static 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 { // ignore right search space high = mid - 1; } } // check if high can be the answer if (totalDigits(high) <= N) { System.out.println(high); } // else low can be the answer else if (totalDigits(low) <= N) { System.out.println(low); } // else answer will be zero. else { System.out.println(0); } } public static void main(String[] args) { int N = 11; // Function call findMaximumLength(N); int N1 = 189; // Function call findMaximumLength(N1); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code for the above approachimport math# Function to count total number# of digits from numbers 1 to Ndef totalDigits(N): cnt = 0 for i in range(1, int(math.log10(N)) + 2): cnt += (N - (10**(i-1)) + 1) return cnt# Function to find Maximum length of# Sequence that can be formed from cost# Ndef findMaximumLength(N): low = 1 high = 10**9 while high - low > 1: 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: # ignore right search space high = mid - 1 # Check if high can be the answer if totalDigits(high) <= N: print(high) # else low can be the answer elif totalDigits(low) <= N: print(low) # else answer will be zero. else: print(0)# Driver codeN1 = 11findMaximumLength(N1)N2 = 189findMaximumLength(N2)# This code is contributed by Potta Lokesh |
C#
// c# implementationusing System;namespace ConsoleApp{ class Program { // Function to count total number of digits from numbers // 1 to N static int TotalDigits(int N) { int cnt = 0; for (int i = 1; i <= N; i *= 10) { cnt += (N - i + 1); } return cnt; } static void FindMaximumLength(int N) { int low = 1, high = 1000000000; 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 { // ignore right search space high = mid - 1; } } // check if high can be the answer if (TotalDigits(high) <= N) { Console.WriteLine(high); } // else low can be the answer else if (TotalDigits(low) <= N) { Console.WriteLine(low); } // else answer will be zero. else { Console.WriteLine(0); } } static void Main(string[] args) { int N = 11; // Function Call FindMaximumLength(N); int N1 = 189; // Function call FindMaximumLength(N1); } }}// This code is contributed by ksam24000 |
Javascript
// Javascript program for above approach// Function to count total number// of digits from numbers 1 to Nfunction totalDigits( N){ let cnt = 0; for (let 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// Nfunction findMaximumLength( N){ let low = 1, high = 1e9; while (high - low > 1) { let 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 { // ignore right search space high = mid - 1; } } // Check if high can be the answer if (totalDigits(high) <= N) console.log(Math.ceil(high)) ; // else low can be the answer else if (totalDigits(low) <= N) console.log(Math.ceil(low)); // else answer will be zero. else console.log(0);}// Driver Code let N = 11; // Function Call findMaximumLength(N); let N1 = 189; // Function call findMaximumLength(N1); // This code is contributed by poojaagarwal2. |
10 99
Time Complexity: O(logN2) (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:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
