How to get the least number after deleting k digits from the input number

Question

For example, if the input number is 24635, the least number is 23 after deleting any 3 digits.

It's not the same as taking the two smallest digits, because the order of the digits must be maintained.

Answer 1

The idea is to traverse through the string from the beginning and remove the first digit which is greater than the digit following it. If no such digit exists, remove the last digit.

    class Solution {
    private:
        void removeOneDigit(string& s){
            for(int i=0; i<s.length()-1; i++){
                if(s[i+1]<s[i]){
                    s.erase(i,1);
                    return;
                }
            }
            s.erase(s.length()-1,1);
        }
    public:
        string removeKdigits(string num, int k) {
            for(int i=0; i<k; i++){
                removeOneDigit(num);
            }
            int i=0;
            while(num[i]=='0'){
                num.erase(0,1);
            }
            if(num.length()==0){return "0";}
            return num;
        }
    };

Answer 2

To solve this, you can follow these steps −

• Define a stack st, create an empty string ret

• n := size of num

• for i in range 0 to n – 1

• while k is non zero and stack is not empty and top of stack > num[i]

• delete from the stack and decrease k by 1

• insert num[i] into st

• while k is not 0, delete element from the stack

• while the stack is not empty

• ret := ret + top of stack, delete element from stack

• now reverse the ret string

• ans := an empty string, and i := 0

• while i < size of ret and ret[i] is not ‘0’

• increase i by 1

• for i < size of ret

• ans := ans + ret[i]

• ret := ans

• return “0” if size of ret is 0, otherwise, ret

C++ solution:

class Solution {
public:
   string removeKdigits(string num, int k) {
      stack st;
      string ret = "";
      int n = num.size();
      for(int i = 0; i < n; i++){
         while(k && !st.empty() && st.top() > num[i]){
            st.pop();
            k--;
         }
         st.push(num[i]);
      }
      while(k--)st.pop();
      while(!st.empty()){
         ret += st.top();
         st.pop();
      }
      reverse(ret.begin(), ret.end());
      string ans = "";
      int i = 0;
      while(i <ret.size() && ret[i] == '0')i++;
      for(; i < ret.size(); i++)ans += ret[i];
      ret = ans;
      return ret.size() == 0? "0" : ret;
   }
};

Answer 3

#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <iostream>
#include <utility>
#include <algorithm>
#define mod 1000000007
#define ll long long
using namespace std;
bool Compare (pair<int, int> p1, pair<int, int> p2)  {
    if (p1.first < p2.first) {
        return true;
    }
    return false;
}
int main() {
    priority_queue <pair<int, int>, vector <pair <int, int> >, function<bool (pair <int, int>, pair <int, int>) > > pq (Compare);
    int n, k;
    cin>>n>>k;
    int i = 1;
    while (n) {
        pq.push(make_pair(n%10, i));
        n = n/10;
        i++;
    }
    for(int j =1; j<=k;j++){
        pq.pop();
    }
    int number = pq.top().first;
    int index = pq.top().second;
    int digit = 1;
    pq.pop();
    while(!pq.empty()){
        int current_index = pq.top().second;
        digit = digit * 10;
        if(current_index < index) {
            number = number * 10 + pq.top().first;
        } else {
            number = digit * pq.top().first + number;
        }
        pq.pop();
    }
    cout<<number<<endl;
    return 0;
}

I solved the question using priority_queue with pair. please let me know if there is any better solution

Answer 4

The idea is based on the fact that a character among first (n+1) characters must be there in resultant number. So we pick the smallest of first (n+1) digits and put it in result, and recur for remaining characters. Below is complete algorithm.

Initialize result as empty string i.e. res = ""

buildLowestNumber(str, n, res)

1) If n == 0, then there is nothing to remove. Append the whole 'str' to 'res' and return

2) Let 'len' be length of 'str'. If 'len' is smaller or equal to n, then everything can be removed. Append nothing to 'res' and return

3) Find the smallest character among first (n+1) characters of 'str'. Let the index of smallest character be minIndex. Append 'str[minIndex]' to 'res' and recur for substring after minIndex and for n = n-minIndex

buildLowestNumber(str[minIndex+1..len-1], n-minIndex).

#include<iostream>
using namespace std;

// A recursive function that removes 'n' characters from 'str'
// to store the smallest possible number in 'res'
void buildLowestNumberRec(string str, int n, string &res)
{
    // If there are 0 characters to remove from str,
    // append everything to result
    if (n == 0)
    {
        res.append(str);
        return;
    }

    int len = str.length();

    // If there are more characters to remove than string
    // length, then append nothing to result
    if (len <= n)
        return;

    // Find the smallest character among first (n+1) characters
    // of str.
    int minIndex = 0;
    for (int i = 1; i<=n ; i++)
        if (str[i] < str[minIndex])
            minIndex = i;

    // Append the smallest character to result
    res.push_back(str[minIndex]);

    // substring starting from minIndex+1 to str.length() - 1.
    string new_str = str.substr(minIndex+1, len-minIndex);

    // Recur for the above substring and n equals to n-minIndex
    buildLowestNumberRec(new_str, n-minIndex, res);
}

// A wrapper over buildLowestNumberRec()
string buildLowestNumber(string str, int n)
{
    string res = "";

    // Note that result is passed by reference
    buildLowestNumberRec(str, n, res);

    return res;
}

// Driver program to test above function
int main()
{
    string str = "121198";
    int n = 2;
    cout << buildLowestNumber(str, n);
    return 0;
}

Answer 5

Very simple Algorithm come to mine mind

1. Consider input number as string
2. Start backward looping from number 9 to 0
3. check if 9 exist in given number(in java we can do it with indexOf()), if exists remove. check if number of removed digit are equal to no of input digits to b removed . If not , check 9 existence gaain till it does not exist (indexOf() will return -1 under java) to see if same digit is repeated . Now repeat if for 8 till expected no of digit are removed
4. Till now we have removed digit which could contribute to larger number
5. Now loop over from 0 to 9 and check if each digit present in number got in step 3 and rearrange it in ascending order

For example :-

Given number is 24635 and no of digit to remove are 2

1. Start from 9, you find first digit to be removed is 6 then 5
2. Remaining number is 243
3. Start loop from 0 to 9 rearrange it in ascending order like 234

Answer 6

private static int getLeastNumberAfterDelete(int num, int dighitsDel) {
 String s = "";
 char[] charArray = String.valueOf(num).toCharArray();
 Arrays.sort(charArray); // Sort charArray
 for (int i = 0; i < (charArray.length - dighitsDel); i++) {
 s += charArray[i];//concatenate 
 }
 return Integer.valueOf(s);
 }

Answer 7

Deleting k digits means keeping n - k digits, where n is the total number of digits.

Use a stack that you keep sorted ascendingly. You remove elements from it as long as you can still make it to n - k digits and your current element is smaller than the top of the stack:

push(2) => 2
push(4) because 2 < 4 => 24
push(6) because 4 < 6 => 246
pop() because 3 < 6 and we can still end up with 2 digits => 24
pop() for the same reason => 2
push(3) => 23
push(5) => 235

Then just take the first k digits => 23. Or you can make sure never to push more than k digits, and then the final stack is your solution.

Note that you cannot pop elements if that means you will not be able to build a solution of k digits. For this, you need to check the current number of elements in the stack and the number of digits to the right of your current position on the input number.

Pseudocode:

stack = []
for each d in digits:
  while !stack.empty() and d < stack.top() and (*):
    stack.pop()

  if stack.size() < n - k:
    stack.push(d)

 (*) - exercise, fill in the condition that prevents you 
       from popping elements if you still want to be able to get to a solution.
 Hint: count how many elements the for loop went over already
       and see how many are left. Also consider how many you have left in the stack.

Since each element enters and leaves the stack at most once, the complexity is O(n).

Answer 8

Knowing that you want to keep digit order certainly makes this solution more difficult.

I do agree with IVlad that char[]s are not the way to go.

I think this is a fairly good solution:

#include <stdio.h>
#include <math.h>
#include <limits.h>

#define DIGITS_TO_REMOVE 3 // Assumed to be positive

int recurse(int* foo, int begin, int end, int previous, int max){
    int i;
    int min = begin;

    for (i = begin; i <= end; ++i){
        if (foo[min] > foo[i]){
            min = i;
        }
    }

    return previous * pow(10, max - end + 1) + (max > end ? recurse(foo, min + 1, end + 1, foo[min], max) : foo[min]);
}

int main(void) {
    int foo[(const int)ceil(log10(INT_MAX))];
    int bar = 24635; // Assumed to be larger than pow(10, DIGITS_TO_REMOVE) - 1
    int size = ceil(log10(bar));
    int i;
    int min = size - DIGITS_TO_REMOVE;

    for (i = 1; bar > 0; bar /= 10, ++i){
        foo[size - i] = bar % 10;

        if (i >= DIGITS_TO_REMOVE && foo[size - i] <= foo[min]){
            min = size - i;
        }
    }

    printf("%d", recurse(foo, min + 1, DIGITS_TO_REMOVE + 1, foo[min], size - 1));
    return 0;
}

EDIT:

IVlad also suggested that I make the solution return an array rather than just an int so it wouldn't be constrained to the size of the return type. There is obviously some work that would need to go into preparing the input and output array so that may not be the goal of the OP, but it's an interesting problem.

#include <stdio.h>

#define DIGITS_TO_REMOVE 3 // Assumed to be positive
#define INPUT_SIZE 5 // Assumed to be greater than DIGITS_TO_REMOVE

void recurse(int* input, int* output, int begin, int end){
    int i;
    int min = begin;

    for (i = begin; i < end; ++i){
        if (input[min] > input[i]){
            min = i;
        }
    }
    output[end - DIGITS_TO_REMOVE - 1] = input[min];

    if (end < INPUT_SIZE){
        recurse(input, output, min + 1, end + 1);
    }
}

int main(void) {
    int foo[] = { 2, 4, 6, 3, 5 };
    int bar[INPUT_SIZE - DIGITS_TO_REMOVE];
    int i;

    recurse(foo, bar, 0, DIGITS_TO_REMOVE + 1);

    for (int i = 0; i < INPUT_SIZE - DIGITS_TO_REMOVE; ++i){
        printf("%d", bar[i]);
    }
    return 0;
}

Answer 9

Offer a recursive approach.

On each iteration test for success k == 0 ...
or failure num == 0 as there are no digits left to remove.
(returning 10 is worse than some other path that would return num.)

Otherwise recurse in 2 ways:
1) Keep the least-significant-digit and try with upper digits.
2) Drop the least-significant-digit and try with upper digits, k--
Return the better one.

unsigned reduce(unsigned num, unsigned k) {
  if (k <= 0) {
    return num;  // Success
  }
  if (num == 0) {
    return 10;  // Fail
  }
  unsigned path1 = reduce(num/10, k)*10 + num%10;
  unsigned path2 = reduce(num/10, k-1);
  return path1 < path2 ? path1 : path2;
}

int main(void) {
  printf("%u\n", reduce(246, 2));
  printf("%u\n", reduce(24635, 3));
  printf("%u\n", reduce(53642, 3));
  printf("%u\n", reduce(21, 1));
}

2
23
32
1

This solution does not depend on knowing the number of digits, just the number needed to remove.

Answer 10

Very simple solution.

We have n digits, and we must remove k of them to leave n-k. We can easily identify what the first digit will be.

The final n-k-1 digits clearly cannot be the first digit of the answer, there simply aren't enough digits after to make a sufficiently long enough number.

We therefore simply ignore the final n-k digits, and focus on the first k digits and find the smallest digit in that collection of k digits. That will be the first digit of our answer. e.g. all three-digit numbers 5XX are smaller than all number of the form 6XX, regardless of what the Xs are. (If there is a tie, where two digits share the honour of being smallest, then choose the number on the left as it gives you more flexibility later.)

Now you know what the first digit is, you can ignore it and everything to the left and repeat the whole thing recursively with the remaining digits - what is the smallest number I can make out of the remaining digits?