HiddenNumbers

SRM 220 · 2004-11-23 · by Kawigi

SRM 220 · 2004-11-23 · by Kawigi · Simple Search, Iteration, String Manipulation, String Parsing

Show categories

Class Name: HiddenNumbers

Return Type: String[]

Method Name: findAll

Arg Types: (vector<string>)

Problem Statement

You are part of a data-mining operation that only cares about numbers as data. As such, you have been assigned to write a program that gets a long chunk of text and searches for all the numbers in the text. Because your boss cares more about large numbers, he only wants you to give him the larger half of the numbers.

You are given a String[] text, the lines of text to be searched for numbers, and you are to find and return the larger half of the numeric substrings in text. Numeric substrings should never overlap, and you should always use the longest possible contiguous sequence of numbers. For instance, "sk12345fj" has just one numeric substring - "12345". "sk12 345fj" has 2 - "12" and "345". If there are an odd number of numeric substrings in text, you will return (n+1)/2 strings. These numbers should be sorted in ascending order of numeric value, and returned with any leading zeros intact. If two numbers found in text have the same numeric value but have different numbers of leading zeros, the one with fewer leading zeros should be considered "less". It is possible for numbers to wrap across lines - if one line ends in a number and the next one begins with a number, these are consecutive parts of the same number.

Notes

While the input will be no more than 50 elements, your return value may have more than 50 elements.

Constraints

text will have between 0 and 50 elements.
Each element in text will have between 0 and 50 characters.
Each element of text will contain only digits ('0'-'9'), letters ('a'-'z', 'A'-'Z'), and spaces (' ').
All of the numbers hidden in text will be between 0 and 263-1, but they may have leading zeros.

Examples

{"098m03r9f80239802389f0m9KDKLKLJDKLJm0983m890DMOm03",
 "dlkfj3hljf4h3klhl  4j4 444 44  rjhkrrkr34534539893",
 " 390804980498409480 dkldjkl djkl djkl d00000002998"}
Returns: { "9",  "44",  "098",  "444",  "890",  "0983",  "00000002998",  "34534539893",  "80239802389",  "390804980498409480" }

Most of the omitted numbers are one-digit numbers.

{"39 000220 30 skldjdije939939slkk 3090 2912kjdk3949",
 "dlkjd dkljsl098 dkd3 23kdkdkl 0000002222kdjdie9000"}
Returns: { "0000002222",  "2912",  "3090",  "3949",  "9000",  "939939" }

Be careful about using the length of the string to compare the numeric values - leading zeros can mess you up!

{}
Returns: { }

This is a shorter one.

{ "iTSvkGl7tjJo2Wx", "SbzWYrcsoEbsriZh7ibDBdsYJHHsb4 wMEy0oOW9cG6", "Mw4nx9dI", "jk5TrTC hbrGEWyKqdoS1iOLJNNJf9", "uoJ3HCQjObHN t700bl B8zKcyzJf5W569vjeeGPSO5veFga", "0b8wYPDGXKaj73oBmnmTKSmPJsAYJNIvmyVr5ja", "VHPncMDq3YXOJ8DtnnJXg5WcUXoMah", "FyoiUeqDxO4G", " FvQQT9DcBP9tmHQtI9um5Kq63", "SgeOKMvUmDWMKrZc5jzphNrgwGhnSVm519vfxdl3v", "VseDImtApmUyqQ8B F3lM3ebtTF8m0rWxJybMM5YxoBco27", "anzpNiyyz7b0ubayVyUFE5VJjFARzkcgqdLkK6lpBElf", "qHhYu4hEs8UVWU3O 334r2Lyk KwyGEdcBnW2iJm", "xKQma2T0mOhUueSuOwtvobw Odfdrgol2ssly345gqzhCMx", "jY5pW q4y0", "rnYriBa1K0UV0 nwxoU9QD70aTA6oMGJENl", "mb8NcOWndKiPDBPYkcPHF6oR", "u0ZCW7iDfcpXc64BQJmylNYmPCp71u2xE0fBZhfua", "BBunWB76OxVSnNKgzEkBjQaGxai", "eEcA5qbhVyB8kxJP8dbc", "ZOkZZ9Mnjfg", "m", "fJGAR9cmfvWLiVV2sVAnGOqq", "rP1", "HVosWjqKcAHnzx i8XQJBUDMRj", "GrTSUnv7KmWXAI6", " WSiPrzUH2VfTJ5FO8Turk7", "lLS5A7OOsQxoQeRVDkZ1E0z8wMEK", "8Ti", "bIYrOZ0qp3erEBv", "CNUBX F2CCzo", "x10pRFrn0DIN", "yhDqgO9JiSoDh2RD9NFc3UywaQerWhHdAhjd pEo", "d0n7nCDlI4qeo0VEspeuz3kdyEJ3ALn5jIHHUpUld", "nW9DyVCCr5X5tezltddQmO6kUoHHkFOdrtv33aax XzreRBT", "tx3lbKAygtG1ftPVDawY1 tL jGMCs0ykxBevpg94a", "gV1U2whB Gt5RA92bjjjdht", "D1IF8wUrs2CZi", "wtoutuhnEojp05gtQfQ52jZK4KBxzqTjCk", "BqyIvGrJupw7Ei8dtsRObRgTVrjs140", "3HwyWzdW95 to", "cG0ziUxL", "vQnhdy8UiXeNg7gQPZjN1CV vqQpQZyE", "FyX6QY6jXpW0VVouVcXna24mv5swPuNtv6hkpa", "o187pJGf7L8l3Ua2Eqd7N8B8Aj6saXshRujBBRHsjYv8", "Om", " nbHYUqrUlWMW9E3A6kxCclztMxnkuIn2pkuWaUvnRO", "eKSRjK17Y7TvApBTMTf7zANBeEvIjYzJyR0zmZNPoD6QeGAln", "XhHiiPDrDW4T" }
Returns: { "05",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "10",  "17",  "24",  "27",  "33",  "52",  "63",  "64",  "70",  "71",  "73",  "76",  "92",  "94",  "95",  "187",  "334",  "345",  "519",  "569",  "700",  "1403" }

{ "UBt1ycW01HshMPyLui", "4rW8", "F6iBTj2XWX6YlKjJE flOsK0AHUeBGprLT06Ybw", "bJq3iraOhJfnYZIO7NjOE", "APhdYjPtLew05uJmi73NmLT3LIBy8bbr8Q7", "nsZtKZYHDrALqegdOnnsFC4KlpniDC", "scfJbeuJjn9Gn", "8CKekZ3xmHrHFLrWPQAYdg0j2o8H 5QVnVKoZ", "f6zDJx7kYJqhu0i4E9UuxtWNw6lRnN2On", "NdA", "WOcfCMjQGth91esN8BokQ20ObpzNUib1x9ng2YMMUx2b6yoW", "opbUoMWIEPiKWkxastl9UsRfaCbPlmzUpRCRFzkvtipXe8", "GRknZgj1hsfWlYjfr2c6Hi8zfMR87w izW ", "3LuuIjS922D5d", "  wstFZqRteIM1ebnZBUgqwfwOAq4MgVca", "qunITcd9Vk5zS4JYQoPhB4C5w", "K VBPT7UKsUGgFq82F1vyjJAFML6WKJvDJ9AJ", "XlPuuuWtKkP", "NhZzZglQT7Mofu3hi7u6RQKJ70KF0OamTN6D9EjqIW6L72z", "l0cSGm xhVhjHNc u5MOMZZ1CmsupHLr8llHHLWDarpmm", "eQb16tA2Rc4cFPMwULVhSUuW", "oEXKIY1QKoze2 VVsbjZfeNxkj1B", "YbzguGfH4JfQLqkaM3omx8mw8Jt", "u1PeJWCtVUgBEu", "Z3XNb vxRni1YuA0pzxdbDuR5e6DCPxrzbdNMfrNSRzjVo4r", "jjUwDjF7UF6Y8ppxvo1T4YhaL4EyQPGU1A", "TNoM8IvaeQ51JimG2I3nuhEWPMiixJlxdHPtQhjN3zw", "mEzGEZWEN7x4KgSIZyNJRZL68MHJY", "jfOracMvvY ", "oMS45GUt5HN8zXnVNVv8GgHHlr0b7ZHOmD7rmZW9nykFab", "c7cFpCc82YzNUJJkfxrI1JoxaYPQgK9Wnzd", "BsAiArZIpZwxcDJpdWUfpRp", "ABWqaFzRAtK7TNOgCP6IqXy7ENb HtDgTh5khekOF", "Tsk3IOYj8U5wExWKjRPEHbe3J5B7EM19rjAXMJayIRHwCe", "JJRARarJtI7IhLfjbFjuAQTa np4XzQSese", "J Q9ifPA06FAjrD", "MXji1e3RCUD7DxOrKzmOEHLBCOwk7qTxd99LCkQZencGLPAxi2", "tpucM6kN1HnwyerTlrlpDUpxlMQOmR3NTQwNcjqwC0Gi", "B0Gj5uohKDcJe" }
Returns: { "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "6",  "06",  "06",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "7",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "8",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "9",  "16",  "19",  "20",  "45",  "51",  "68",  "70",  "72",  "73",  "82",  "82",  "87",  "91",  "99",  "922" }

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HiddenNumbers with a public method vector<string> findAll(vector<string> text) · 77 test cases · 2 s / 256 MB per case