Big Sorting, a HackerRank problem

-
Here is the link to the problem: https://www.hackerrank.com/challenges/big-sorting, and the description copied/pasted:

Consider an array of numeric strings, , where each string is a positive number with anywhere from  to  digits. Sort the array's elements in non-decreasing (i.e., ascending) order of their real-world integer values and print each element of the sorted array on a new line.

The numbers will be massive, up to 10^6 digits. One option is to use the BigInteger data type, but operations with BigIntegers are very slow. The other one, which is the one that I had opted to use, uses the Array.Sort() method in C#. The only caveat here is to implement the IComparer.Compare method. In our case it is very easy to implement since the inputs are in string format, with no leading zero. The key part of the code in my opinion is the implementation of this function, the rest is just syntax. Thanks, Marcelo.


using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Collections;
class Solution
{
    public class myCompareClass : IComparer
    {
        int IComparer.Compare(Object x, Object y)
        {
            string s1 = (string)x;
            string s2 = (string)y;

             if (s1.Length < s2.Length) return -1;
            if (s1.Length > s2.Length) return 1;

             for (int i = 0; i < s1.Length; i++)
            {
                if (s1[i] < s2[i]) return -1;
                if (s1[i] > s2[i]) return 1;
            }

             return 0;
        }

     }
    static void Main(String[] args)
    {
        int n = Convert.ToInt32(Console.ReadLine());
        string[] unsorted = new string[n];
        for (int unsorted_i = 0; unsorted_i < n; unsorted_i++)
        {
            unsorted[unsorted_i] = Console.ReadLine();
        }

         myCompareClass myCompare = new myCompareClass();
        Array.Sort(unsorted, myCompare);

         for (int i = 0; i < n; i++)
        {
            Console.WriteLine(unsorted[i]);
        }
    }
}

Comments

  1. TarasMay 2, 2017 at 11:23 PM

    this sounds like a perfect fit for a radix sort, but I couldn't resist a temptation to cheat and use a built-in sort with custom comparator too :)

    #include
    #include
    #include
    #include
    using namespace std;

    int main() {
    int n; cin >> n;
    vector strings(n);
    for (int i = 0; i < n; ++i) cin >> strings[i];
    sort(strings.begin(), strings.end(), [](const string& s1, const string& s2) {
    if (s1.size() < s2.size()) return true;
    if (s1.size() > s2.size()) return false;
    return s1 < s2;
    });
    copy(strings.cbegin(), strings.cend(), ostream_iterator(cout, "\n")); cout << endl;
    return 0;
    }

    http://ideone.com/ScAC6m

    ReplyDelete
    Replies
    1. Marcelo M De BarrosMay 3, 2017 at 9:06 AM

      The inline function is so cool! Good job, buddy!!!

      Delete
    2. TarasMay 3, 2017 at 10:23 AM

      yep, it's awesome to see C++ getting modern and maintaining its zero-overhead abstractions principle :)

      Delete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed as the sum of the cubes of  .  . There is no other way to express   as th
Read more