Why is my program unable to sort integer strings?

Question

I was trying to solve a very simple coding question:

Consider an array of numeric strings where each string is a positive number with anywhere from 1 to 10^6 digits. Sort the array's elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line.

The first line contains an integer n denoting the number of strings Each of the n subsequent lines contain an INTEGER STRING.

My code is:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int i; string s;
    cin >> i;
    int j = i;
    string arr[i];
    int cntr = 0;
    while (i--){
        cin >> s;
        arr[cntr] = s;
        cntr++;
    }
    sort(arr, arr+j);

    for (auto c: arr)
        cout << c << endl;

}

The input is

6
31415926535897932384626433832795
1
3
10
3
5

And my output turns out to be:

1
10
3
3
31415926535897932384626433832795
5

If I make an array and add integer strings to it manually, the above code works fine. Then why is it producing wrong result when it takes input from the website?

PS: Here's the link to the problem:https://www.hackerrank.com/challenges/big-sorting/problem

Answer 1

Firstly use a vector of strings instead of a variable size array of strings (which is not allowed in C++).

The STL sort function uses lexicographical search to sort strings by default. You need to pass your own comparison function in order to sort the integer strings numerically.

Assuming the integer strings don't have leading 0's;

sort(arr.begin(), arr.end(), [] (const string& s1, const string& s2) {
    return s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2);
});

Answer 2

I will give you an alternative solution as C++ already have sorted containers.

Some hints: Please do not use "using namespace std;"

C++ did not have variable length arrays! So it is much easier to use a container type! In the example, we use a std::multimap which can have elements sorted and allows duplicates.

#include <iostream>
#include <map>

// we want to use our own sorting algorithm for std::multimap
// this needs a functional object with operator() which do the compare
//
// works only for non negative numbers without leading '0's
struct compare
{
    bool operator()( const std::string& s1, const std::string& s2 ) const
    {
        // if the string contains a number as text, we can asume that
        // a number which has less characters is lesser
        if ( s1.size() < s2.size() ) return true;

        // if the size is bigger, the numerical value is bigger
        if ( s1.size() > s2.size() ) return false;

        // if both are equal length
        // so we simply compare lexigraphical
        // this works because a bigger diggit char always means a
        // bigger numerical value
        return s1 < s2;
    }
};

int main()
{
    // instead of later sort, we use a sorted container, multiset because we can use duplicates
    std::multiset<std::string, compare> data;

    // read data as in your code 
    int numberOfElementsToRead;
    std::string tmpInput;

    std::cin >> numberOfElementsToRead;

    while (numberOfElementsToRead--)
    {
        std::cin >> tmpInput;
        data.insert( tmpInput ); // insert automatically sorts
    }

    // print out the container
    for ( auto& s: data )
    {
        std::cout << s << std::endl;
    }
}

Answer 3

This won't work:

    int i;
    cin >> i;

    string arr[i];

If you need to dynamically resize an array, use std::vector (or new/delete if you really must).

    int i;
    cin >> i;

    std::vector<std::string> arr(i);

In terms of why the sorting fails, you are sorting the numbers alphabetically, which means anything with a '1' at the front will appear first. Sort based on the numeric value instead:

auto compareStringsNumerically = [](const std::string& a, const std::string& b) {
  return std::stoi(a) < std::stoi(b); //< compare integer values
};
std::sort(arr, arr + j, compareStringsNumerically);