# Hidden unique integers

See the original problem on HackerRank.

## Solutions

A solution consists in finding all the contiguous digits in the string, converting them to integers and putting them in a set for removing duplicates. Finally, outputting the size of the set:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  int n; cin >> n; string input; while (n--) { cin >> input; set integers; auto cur = begin(input); while (cur != end(input)) { if (cur = std::find_if(cur, end(input), ::isdigit); cur != input.end()) { const auto digitEnd = std::find_if_not(cur, end(input), ::isdigit); integers.insert(std::stoi(std::string(cur, digitEnd))); cur = digitEnd; } } cout << integers.size() << "\n"; } 

This solution can be redesigned by using C++ ranges. We note that “contiguous digits” are actually “chunks” of characters that are all digits. This means, we can apply views::chunk_by to obtain contiguous sequences of characters that are all of the same “alphabeticalness”. Then we just filter out those which are not digits, convert all the remaining ranges to integers, and finally construct a set from of the resulting range of numbers:

 1 2 3 4 5  std::cout << size(input | views::chunk_by([](auto a, auto b) { return isalpha(a) == isalpha(b); }) | views::filter([](auto rng) { return isdigit(at(rng, 0)); }) | views::transform([](auto rng) { return std::stoi(to(rng)); }) | to); 

Strictly speaking, isalpha(a) == isalpha(b) might be false even though both characters are alphabetical because isalpha() returns any positive number if the input is a letter. However, most implementations just return the very same value for every letter and 0 otherwise. Thus, we should raplace that check with something like (bool)isalpha(a) == (bool)isalpha(b).

An extension of this solution consists in handling numbers that are out of built-in integral bounds (e.g. int and size_t). This is possible by removing leading zeros from extracted numbers and store them in the set (of strings):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  int n; cin >> n; string input; while (n--) { cin >> input; set numbers; auto cur = begin(input); while (cur != end(input)) { if (cur = std::find_if(cur, end(input), ::isdigit); cur != s.end()) { const auto digitEnd = std::find_if_not(cur, s.end(), ::isdigit); std::string digit(cur, digitEnd); digit.erase(0, digit.find_first_not_of('0')); // remove leading zeros numbers.insert(digit); cur = digitEnd; } } cout << numbers.size() << "\n"; } 

Here is the same idea with ranges:

 1 2 3 4 5 6  std::cout << size(input | views::chunk_by([](auto a, auto b) { return isalpha(a) == isalpha(b); }) | views::filter([](auto rng) { return isdigit(at(rng, 0)); }) | views::transform([](auto rng) { return views::drop_while(rng, [](auto c){ return c=='0'; }); } ) | views::transform([](auto rng) { return to(rng); }) | to); 
comments powered by Disqus