SG Newsletter

Share this post

Coding Interview Question: Find the greatest integer smaller than N with the same set of digits as N (C++ Solutions with O(n ^ 2) and O(n) time complexities)

serhatgiydiren.substack.com

Coding Interview Question: Find the greatest integer smaller than N with the same set of digits as N (C++ Solutions with O(n ^ 2) and O(n) time complexities)

Google, Meta, Amazon Interview Questions

Serhat Giydiren
Oct 20, 2022
1
Share this post

Coding Interview Question: Find the greatest integer smaller than N with the same set of digits as N (C++ Solutions with O(n ^ 2) and O(n) time complexities)

serhatgiydiren.substack.com

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;
}

The original post is here.

Thank you for reading SG Newsletter. This post is public so feel free to share it.

Share

Thanks for reading SG Newsletter! Subscribe for free to receive new posts and support my work.

Share this post

Coding Interview Question: Find the greatest integer smaller than N with the same set of digits as N (C++ Solutions with O(n ^ 2) and O(n) time complexities)

serhatgiydiren.substack.com
Previous
Next
Comments
TopNew

No posts

Ready for more?

© 2023 Serhat Giydiren
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing