Program to find minimum number in string

Question

I have a c# class like so

internal class QueuedMinimumNumberFinder : ConcurrentQueue<int>
{
    private readonly string _minString;
    public QueuedMinimumNumberFinder(string number, int takeOutAmount)
    {
        if (number.Length < takeOutAmount)
        {
            throw new Exception("Error *");
        }
        var queueIndex = 0;
        var queueAmount = number.Length - takeOutAmount;
        var numQueue = new ConcurrentQueue<int>(number.ToCharArray().Where(m => (int) Char.GetNumericValue(m) != 0).Select(m=>(int)Char.GetNumericValue(m)).OrderBy(m=>m));
        var zeroes = number.Length - numQueue.Count;
        while (queueIndex < queueAmount)
        {
            int next;
            if (queueIndex == 0)
            {
                numQueue.TryDequeue(out next);
                Enqueue(next);
            } else
            {
                if (zeroes > 0)
                {
                    Enqueue(0);
                    zeroes--;
                } else
                {
                    numQueue.TryDequeue(out next);
                    Enqueue(next);
                }
            }
            queueIndex++;
        }
        var builder = new StringBuilder();
        while (Count > 0)
        {
            int next = 0;
            TryDequeue(out next);
            builder.Append(next.ToString());
        }
        _minString = builder.ToString();
    }

    public override string ToString() { return _minString; }
}

The point of the program is to find the minimum possible integer that can be made by taking out any x amount of characters from a string(example 100023 is string, if you take out any 3 letters, the minimum int created would be 100). My question is, is this the correct way to do this? Is there a better data structure that can be used for this problem?

First Edit:

Here's how it looks now

 internal class QueuedMinimumNumberFinder
    {
        private readonly string _minString;
        public QueuedMinimumNumberFinder(string number, int takeOutAmount)
        {
            var queue = new Queue<int>();
            if (number.Length < takeOutAmount)
            {
                throw new Exception("Error *");
            }
            var queueIndex = 0;
            var queueAmount = number.Length - takeOutAmount;
            var numQueue = new List<int>(number.Where(m=>(int)Char.GetNumericValue(m)!=0).Select(m=>(int)Char.GetNumericValue(m))).ToList();
            var zeroes = number.Length - numQueue.Count;
            while (queueIndex < queueAmount)
            {
                if (queueIndex == 0)
                {
                    var nextMin = numQueue.Min();
                    numQueue.Remove(nextMin);
                    queue.Enqueue(nextMin);
                } else
                {
                    if (zeroes > 1)
                    {
                        queue.Enqueue(0);
                        zeroes--;
                    } else
                    {
                        var nextMin = numQueue.Min();
                        numQueue.Remove(nextMin);
                        queue.Enqueue(nextMin);
                    }
                }
                queueIndex++;
            }
            var builder = new StringBuilder();
            while (queue.Count > 0)
            {
                builder.Append(queue.Dequeue().ToString());
            }
            _minString = builder.ToString();
        }

        public override string ToString() { return _minString; }
    }

Answer 1

Here's my solution using LINQ:

public string MinimumNumberFinder(string number, int takeOutAmount)
{
    var ordered = number.OrderBy(n => n);
    var nonZero = ordered.SkipWhile(n => n == '0');
    var zero = ordered.TakeWhile(n => n == '0');

    var result = nonZero.Take(1)
                        .Concat(zero)
                        .Concat(nonZero.Skip(1))
                        .Take(number.Length - takeOutAmount);   

    return new string(result.ToArray());
}

Answer 2

Just keep a count of how many times each digit appears. An array of size 10 will do. Count[i] gives the count of digit i.

Then pick the smallest non-zero i first, then pick the smallest etc and form your number.

Answer 3

A pretty simple and efficient implementation can be made, once you realize that your input string digits map to the domain of only 10 possible values: '0' .. '9'.

This can be encoded as the number of occurrences of a specific digit in your input string using a simple array of 10 integers: var digit_count = new int[10];

@MasterGillBates describes this idea in his answer.

You can then regard this array as your priority queue from which you can dequeue the characters you need by iteratively removing the lowest available character (decreasing its occurrence count in the array).

The code sample below provides an example implementation for this idea.

public static class MinNumberSolver
{
    public static string GetMinString(string number, int takeOutAmount)
    {
        // "Add" the string by simply counting digit occurrance frequency.
        var digit_count = new int[10];
        foreach (var c in number)
            if (char.IsDigit(c))
                digit_count[c - '0']++;

        // Now remove them one by one in lowest to highest order.

        // For the first character we skip any potential leading 0s
        var selected = new char[takeOutAmount];
        var start_index = 1;
        selected[0] = TakeLowest(digit_count, ref start_index);

        // For the rest we start in digit order at '0' first.
        start_index = 0;
        for (var i = 0; i < takeOutAmount - 1; i++)
            selected[1 + i] = TakeLowest(digit_count, ref start_index);

        // And return the result.
        return new string(selected);
    }

    private static char TakeLowest(int[] digit_count, ref int start_index)
    {
        for (var i = start_index; i < digit_count.Length; i++)
        {
            if (digit_count[i] > 0)
            {
                start_index = ((--digit_count[i] > 0) ? i : i + 1);
                return (char)('0' + i);
            }
        }
        throw new InvalidDataException("Input string does not have sufficient digits");
    }
}

Answer 4

You could place every integer into a list and find all possible sequences of these values. From the list of sequences, you could sort through taking only the sets which have the number of integers you want. From there, you can write a quick function which parses a sequence into an integer. Next, you could store all of your parsed sequences into an array or an other data structure and sort based on value, which will allow you to select the minimum number from the data structure. There may be simpler ways to do this, but this will definitely work and gives you options as far as how many digits you want your number to have.

Answer 5

If I'm understanding this correctly, why don't you just pick out your numbers starting with the smallest number greater than zero. Then pick out all zeroes, then any remaining number if all the zeroes are picked up. This is all depending on the length of your ending result

In your example you have a 6 digit number and you want to pick out 3 digits. This means you'll only have 3 digits left. If it was a 10 digit number, then you would end up with a 7 digit number, etc...

So have an algorithm that knows the length of your starting number, how many digits you plan on removing, and the length of your ending number. Then just pick out the numbers.

This is just quick and dirty code:

string startingNumber = "9999903040404"; // "100023";
int numberOfCharactersToRemove = 3;

string endingNumber = string.Empty;
int endingNumberLength = startingNumber.Length - numberOfCharactersToRemove;

while (endingNumber.Length < endingNumberLength)
{
    if (string.IsNullOrEmpty(endingNumber))
    {
        // Find the smallest digit in the starting number
        for (int i = 1; i <= 9; i++)
        {
            if (startingNumber.Contains(i.ToString()))
            {
                endingNumber += i.ToString();
                startingNumber = startingNumber.Remove(startingNumber.IndexOf(i.ToString()), 1);
                break;
            }
        }
    }
    else if (startingNumber.Contains("0"))
    {
        // Add any zeroes
        endingNumber += "0";
        startingNumber = startingNumber.Remove(startingNumber.IndexOf("0"), 1);
    }
    else
    {
        // Add any remaining numbers from least to greatest
        for (int i = 1; i <= 9; i++)
        {
            if (startingNumber.Contains(i.ToString()))
            {
                endingNumber += i.ToString();
                startingNumber = startingNumber.Remove(startingNumber.IndexOf(i.ToString()), 1);
                break;
            }
        }
    }
}

Console.WriteLine(endingNumber);

100023 starting number resulted in 100 being the end result

9999903040404 starting number resulted in 3000044499 being the end result

Answer 6

Here's my version to fix this problem:

---

DESIGN:

• You can sort your list using a binary tree , there are a lot of implementations , I picked this one
• Then you can keep track of the number of the Zeros you have in your string Finally you will end up with two lists: I named one SortedDigitsList and the other one ZeroDigitsList
• perform a switch case to determine which last 3 digits should be returned

Here's the complete code:

 class MainProgram2
{
    static void Main()
    {
        Tree theTree = new Tree();
        Console.WriteLine("Please Enter the string you want to process:"); 
        string input = Console.ReadLine();
        foreach (char c in input)
        {
            // Check if it's a digit or not
            if (c >= '0' && c <= '9')
            {
                theTree.Insert((int)Char.GetNumericValue(c));
            }

        }
        //End of for each (char c in input)


        Console.WriteLine("Inorder traversal resulting Tree Sort without the zeros");
        theTree.Inorder(theTree.ReturnRoot());
        Console.WriteLine(" ");

        //Format the output depending on how many zeros you have
        Console.WriteLine("The final 3 digits are");
        switch (theTree.ZeroDigitsList.Count)
        {
            case 0:
                {
                    Console.WriteLine("{0}{1}{2}", theTree.SortedDigitsList[0], theTree.SortedDigitsList[1], theTree.SortedDigitsList[2]);
                    break;
                }
            case 1:
                {
                    Console.WriteLine("{0}{1}{2}", theTree.SortedDigitsList[0], 0, theTree.SortedDigitsList[2]);
                    break;
                }
            default:
                {
                    Console.WriteLine("{0}{1}{2}", theTree.SortedDigitsList[0], 0, 0);
                    break;
                }

        }


        Console.ReadLine();
    }

}//End of main()
 }

class Node
{
    public int item;
    public Node leftChild;
    public Node rightChild;
    public void displayNode()
    {
        Console.Write("[");
        Console.Write(item);
        Console.Write("]");
    }
}
class Tree 
{

public List<int> SortedDigitsList { get; set; }
public List<int> ZeroDigitsList { get; set; }
public Node root;
public Tree()
{

    root = null;
    SortedDigitsList = new List<int>();
    ZeroDigitsList = new List<int>();


}
public Node ReturnRoot()
{
    return root;
}
public void Insert(int id)
{
    Node newNode = new Node();
    newNode.item = id;
    if (root == null)
        root = newNode;
    else
    {
        Node current = root;
        Node parent;
        while (true)
        {
            parent = current;
            if (id < current.item)
            {
                current = current.leftChild;
                if (current == null)
                {
                    parent.leftChild = newNode;
                    return;
                }
            }
            else
            {
                current = current.rightChild;
                if (current == null)
                {
                    parent.rightChild = newNode;
                    return;
                }
            }
        }
    }
}
//public void Preorder(Node Root)
//{
//    if (Root != null)
//    {
//        Console.Write(Root.item + " ");
//        Preorder(Root.leftChild);
//        Preorder(Root.rightChild);
//    }
//}

public void Inorder(Node Root)
{
    if (Root != null)
    {
        Inorder(Root.leftChild);
        if (Root.item > 0)
        {
            SortedDigitsList.Add(Root.item);
            Console.Write(Root.item + " ");
        }
        else
        {
            ZeroDigitsList.Add(Root.item);
        }
        Inorder(Root.rightChild);
    }

}