Finding the largest three-digits number "within" a number

Question

For this question, I need to find the largest three-digit number within a larger number.

Sample Test Case 1:
534535
Output:
535

---

Sample Test Case 2 :
23457888976
Output :
976

---

I've tried the following code:

        #include <iostream>
        using namespace std;
        int main() {
        int num;
        cin>>num;
        int len= to_string(num).length();
        int arr[10],lnum=0,max=0;
        for (int i =len-1;i>=0;i--)
        {
        arr[i] = num%10;
        num =num/10;    //to convert int into array
        }
        for (int i=0;i<len-2;i++)
        {
        if (arr[i] >arr[i+1])
            lnum = arr[i]*100+arr[i+1]*10+arr[i];
        if (lnum>max)
            max= lnum;  
        }
        cout<<max;
        return 0;
    }

---

Although this code seems to work for Test Case 1, it doesn't work for most of the inputs.

---

(Please do help with this too. )
1. This is for numbers with 10-digits only (that too, most of it have wrong output). What to do in case of bigger numbers?
2. Is there any better way to convert the integer into an array? Or will a string array work in similar way?
3. It's really slow, can anyone help me figure out how to speed this up?

---

Thanks for any help !!

Solution 1

#include <iostream>
#include <string>
using namespace std;
int main() {
    int i, n;
    string s;
    cin >> s;
    n = (int)s.size();
    if(n<3){
        /* there are less than 3 digits in the input number
        Here, you can print the number itself as it will be largest number or
        print -1 which can state that no 3 digit number exists.
        */
        cout<<-1;
        return 0;
    }
    int maxans = (s[0]-'0')*100 + (s[1]-'0')*10 + (s[2]-'0');
    // storing the first 3 digits as the maximum answer till now.
    int prev = maxans;
    for(i = 3;i<n;i++){
        int cur = (prev%100)*10 + (s[i]-'0'); // using %100 to extract the last two digits and then multiplying by 10 and adding the ith digit to make the next 3 digit number.
        maxans = max(maxans, cur);
        prev = cur;
    }
    cout<<maxans;
    return 0;
}

This code is of time complexity O(n) where n is the length of input string and space complexity O(1)

Solution 2

This approach will work with any big number you can store in variable. The approach is as follows,

First convert number into string and then create an array of all possible numbers of 3 digits as showed below,

Number = 534535
All possible 3 digits number array = ["534", "345", "453", "535"]

Then sort this array, after sorting last element will be max number of three digit, as highlighted below,
Sorted array = ["345", "453", "534", "535"]

Another example,
Number = 23457888976
All possible 3 digits number array = ["234", "345", "457", "578", "788", "888", "889", "897", "976"]
After sorting, last element is max number as highlighted below
Sorted array = ["234", "345", "457", "578", "788", "888", "889", "897", "976"]

Note: Radix sort will perform better then std::sort(), std::sort() offers Quick sort. Radix sort is ideal for string sorting and specially in this case because max bucket size is only 10 (possible range 0-9), but you have to implement radix sort your self.

#include <iostream>

#include <vector>
#include <string>
#include <algorithm>

using std::cout;

std::vector<std::string> allThreeDigitNumbers(const std::string& numStr){

    std::vector<std::string> allNumStr(numStr.size() - 2, std::string("000"));
    std::vector<std::string>::iterator aIt = allNumStr.begin();

    for(std::string::const_iterator it = numStr.cbegin(), lastIt = it + (numStr.size() - 2); lastIt != it; ++it, ++aIt){

        std::copy(it, it + 3, aIt->begin());
    }

    return allNumStr;
}

unsigned maxThreeDigitNumberInNumber(unsigned long long num){

    std::string numStr = std::to_string(num);

    if(numStr.size() < 3){

        return 0;
    }

    std::vector<std::string> allNumStr = allThreeDigitNumbers(numStr);

    std::sort(allNumStr.begin(), allNumStr.end());

    return std::stoul(allNumStr.back());
}

int main(){
    cout<< "Max 3 digits number of 534535 => "<< maxThreeDigitNumberInNumber(534535)<< '\n';
    cout<< "max 3 digits number of 23457888976 => "<< maxThreeDigitNumberInNumber(23457888976)<< '\n';
}

Output

Max 3 digits number of 534535 => 535
max 3 digits number of 23457888976 => 976

Comments

[IWonderWhatThisAPIDoes]

Analyze them as strings rather than numbers. It's far more straightforward and less likely to produce an error

[neilharia7]

use sliding window algorithm

[Bathsheba]

Hint: n % 1000 extracts the rightmost three digits of n. n /= 10 removes the final digit from n. Don't forget to consider the case of negative n. Your test cases are evil - both largest numbers are at the end. Do test with some more. Another note: using a string method may not be such a bad idea given you are loading from standard input anyway.

[Shinichi]

@IWonderWhatThisAPIDoes thnx, can you help me with the code?

[IWonderWhatThisAPIDoes]

Sure, where did you get stuck? ;)

[Shinichi]

@neilharia7, if we use sliding algo, it'll still not work cause it's the position of the digits, not the sum of the digits that matter. Although, it'll make the process a bit easier. For ex, 287782 might not produce the required output. I'll need another condition to check it once more. But still, thanks

[Shinichi]

@IWonderWhatThisAPIDoes, I'm still working on that. But still, could this way work out somehow?

[IWonderWhatThisAPIDoes]

Are you asking to debug this code? arr[i]*100+arr[i+1]*10+arr[i] is definitely not alright

[Shinichi]

@IWonderWhatThisAPIDoes yes please, any debugs for this code?

[IWonderWhatThisAPIDoes]

arr[i]*100+arr[i+1]*10+arr[i+2]?

[Pete Becker]

The key to a simple solution here is to recognize that this question is about text, not about numeric values as such. Don't read into an int; read into std::string. Search for the highest digit in the string; if there's only one of that digit, you're done. If there's more than one, look at the next digit.

[Shinichi]

@PeteBecker, thanks I got it.