1

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

Improve this question
14
  • 6
    Three things (unrelated to your problem): C++ doesn't have variable-length arrays, use std::vector instead. Also don't include <bits/stdc++.h>. Lastly, don't do using namespace std;. To summarize: Don't use such sites to learn C++, they're infamously bad for it. Take a course or a class or read books. Commented Oct 3, 2019 at 6:50
  • 1
    As for your problem: String comparison is lexiographical not numerical. Commented Oct 3, 2019 at 6:52
  • I am not using variable-length arrays! Commented Oct 3, 2019 at 6:53
  • 1
    int i; followed by string arr[i];. That makes arr a variable-length array. Array sizes in C++ must be compile-time constants. Commented Oct 3, 2019 at 6:54
  • 1
    Because it is text! Nobody knows that you want compare numbers represented as text. Commented Oct 3, 2019 at 7:10

3 Answers 3

Reset to default
5

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);
});
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

@DanielLangr: Ubs! To early in the morning! Thanks!
@DanielLangr Um....I put in the smiley to show it was a joke...
0

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;
    }
}
Improve this answer

4 Comments

Adding data to already sorted containers is faster than collecting all data unsorted and sort them later. I would be very careful with this statement. For example, this benchmark illustrates the exact opposite; namely, insterting into a vector and its subsequent sorting is more than twice as fast. Of course, it's a benchmark, but it shows that we shouldn't make such generic statements.
Relevant answers: stackoverflow.com/a/15638063/580083 and stackoverflow.com/a/24968324/580083. Other migth be interesting as well. A rule of thumb is basically that if one only needs to insert elements and then have them sorted at some moment without future updates, vector + sort would be very likely faster.
sets (and multisets) are usually implemented as balanced binary trees (typically red-black trees). Insertion of element into a red-black tree may violate the properties of the red-black tree and to restore these, there is a requirement of color changes and rotations. So you can imagine why storing the strings in a vector and then sorting it is usually faster than sorting the strings using STL set (and multiset).
@DanielLangr: Removed the "speed" part from my answer. Thanks for the correction!
-4

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);
Improve this answer

5 Comments

your sort comparator wont work as the numbers have up to 10^6 digits which is much larger than an int
Why use more complicated lambda combined with an auto variable instead a good old function. This is abuse of lambda for me!
@Klaus Maybe, because we cannot define a function inside a function?
@DanielLangr: In this case there is no need to define a function inside a function. Lambdas made for 1) write function in place ( not the case here ), or create functional objects which can store data ( also not the case here ). I can't see any benefit here, it is only more complicated.
@Klaus Agree, there is no need. IMO, it's simply a matter of coding style. Discussions about coding styles are usually meaningless. I don't think the generated assembly would be different: godbolt.org/z/Co8VF9. I wouldn't use this approach either, but can see its advantage, i.e., by naming the lambda, a less experienced code reader may find out what it does more easily. (Sure, we have comments, but it's again a matter of coding style.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.