# Coding Interview Question: Find the greatest integer smaller than N with the same set of digits as N

Join me to stay up-to-date and get my new articles delivered to your inbox by subscribing here.

#### October 20, 2022

Table of Contents

## Question

Given an integer N, find the greatest integer less than N and has the same digits. If there is no such integer, return -1.

For example:

Input = 630

Output = 603

Input = 603

Output = 360

Input = 360

Output = 306

Input = 306

Output = -1 (Be careful, 063 could not be an answer, leading zeros are weird, discuss with your interviewer)

## C++ Solution – O(n ^ 2) [Quadratic Time Complexity]

``````int prev_greatest_v1(int num)
{
string strnum = to_string(num);
for(int i = strnum.size() - 1; i > 0; i--)
{
for(int j = i - 1; (strnum[i] == '0' && j >= 1) || (strnum[i] != '0' && j >= 0); j--)
{
if (strnum[j] > strnum[i])
{
swap(strnum[i], strnum[j]);
sort(strnum.begin() + j + 1, strnum.end(), greater <> ());
return stoi(strnum);
}
}
}
return -1;
}``````

## C++ Solution – O(n) [Linear Time Complexity]

``````int prev_greatest_v2(int num)
{
string strnum = to_string(num);

vector < int > track(strnum.size(), -1);
stack < int > s;
for(unsigned i = 0; i < strnum.size(); i++)
{
while(!s.empty() && strnum[s.top()] <= strnum[i]) s.pop();
if (!s.empty()) track[i] = s.top();
s.push(i);
}

for(int i = track.size() - 1; i > 0; i--)
{
if (track[i] != -1 && (strnum[i] != '0' || track[i] != 0))
{
swap(strnum[i], strnum[track[i]]);
sort(strnum.begin() + track[i] + 1, strnum.end(), greater <> ());
return stoi(strnum);
}
}
return -1;
}``````

## Full Code

The code contains some extra blocks related to creating random numbers and checking the return values of two different solutions.

``````// https://serhatgiydiren.com
// Oct 20, 2022

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

mt19937 rng(steady_clock::now().time_since_epoch().count());

// O(n^2) - quadratic time complexity
int prev_greatest_v1(int num)
{
string strnum = to_string(num);
for(int i = strnum.size() - 1; i > 0; i--)
{
for(int j = i - 1; (strnum[i] == '0' && j >= 1) || (strnum[i] != '0' && j >= 0); j--)
{
if (strnum[j] > strnum[i])
{
swap(strnum[i], strnum[j]);
sort(strnum.begin() + j + 1, strnum.end(), greater <> ());
return stoi(strnum);
}
}
}
return -1;
}

// O(n) - linear time complexity
int prev_greatest_v2(int num)
{
string strnum = to_string(num);

vector < int > track(strnum.size(), -1);
stack < int > s;
for(unsigned i = 0; i < strnum.size(); i++)
{
while(!s.empty() && strnum[s.top()] <= strnum[i]) s.pop();
if (!s.empty()) track[i] = s.top();
s.push(i);
}

for(int i = track.size() - 1; i > 0; i--)
{
if (track[i] != -1 && (strnum[i] != '0' || track[i] != 0))
{
swap(strnum[i], strnum[track[i]]);
sort(strnum.begin() + track[i] + 1, strnum.end(), greater <> ());
return stoi(strnum);
}
}
return -1;
}

void process()
{
int num = rng() % INT_MAX;
while(num != -1)
{
int res_v1 = prev_greatest_v1(num);
int res_v2 = prev_greatest_v2(num);
assert(res_v1 == res_v2);
cout << num << " -> " << res_v1 << endl;
num = res_v1;
}
}

void fast_io()
{
ios::sync_with_stdio(false);
srand(time(NULL));
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(2);
cerr << fixed << setprecision(2);
}

int main()
{
fast_io();
process();
return EXIT_SUCCESS;
}``````

Table of Contents

Table of Contents