1. Sort The Array

Given an array arr of n integers, choose any element of the array that has multiple digits and replace it with any substring of the integer. In this context, a substring of an integer is considered as any contiguous segment of digits of the integer. For example, 728, 86, 2, 37 etc. are the substrings of the integer 372862 which 322, 7862 are not.

Sort the array by performing the operation any number of times. Find the lexicographically smallest sorted array possible. If it is not possible to create a sorted array in this manner, report [-1] as the

answer i.e. an array containing a single element, -1.

Note: An array x of length n is lexicographically smaller than an array y of length n if there exists an i (0 < i <n), such that x[i] < y[i], and for anyj (0 ≤ j < 1)x(]=yül.

Example

Suppose n-3 and arr-[9, 112, 425),

It is optimal to delete the digits 2 from 112 and 4 from 425 to get the array [9, 11, 25].

Function Description

Complete the function getSmallestSortedArray in the editor below

getSmallest SortedArray has the following parameter:

int arr[n]: an array of integers

Returns

int[n]: The lexicographically smallest sorted array possible or an array containing a single integer -1 if it is not possible.

Constraints

• 1≤n _<105

• O_< arr[i] _< 109

Sample Input For Custom Testing

STDIN                         FUNCTION                          

3                   -->         arr[]  size n=3

3                 -->         arr = [3,32,4]

32

4

Sample Output

3

3

6

ADD COMMENT • link

Entering edit mode

// by squirtle
vector<int> solve(vector<int> &v){
    int n = v.size();
    for(int i=0; i<n; i++){
        if(i==0){
            int minm=v[0];
            while(v[0]){
                minm = min(minm, v[0]%10);
                v[0]/=10;
            }
            v[0] = minm;
            continue;
        }
        
        int prevlen = to_string(v[i-1]).size();
        string currnum = to_string(v[i]);
        int minm = v[i];
        for(int s=prevlen; s<=prevlen+1; s++){
            for(int k=0; k+s-1<currnum.size(); k++){
                if(stoi(currnum.substr(k, s))>=v[i-1]) 
                    minm = min(minm, stoi(currnum.substr(k, s)));
            }
        }
        if(minm<v[i-1]) return {-1};
        else v[i] = minm;
    }
    return v;
}

int main() {
    vector<int> v = {3, 2642, 54};
    auto ans = solve(v);
    for(auto n: ans) cout<<n<<" ";
    return 0;
}

ADD COMMENT • link 14 months ago squirtle • 20