diff options
author | Jack Sangdahl <[email protected]> | 2025-04-09 20:10:30 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-09 20:11:06 -0600 |
commit | 3db8c23a3d67a84980523cb06a3aa4a5febba291 (patch) | |
tree | aa04ebc65df7386660e63556592d104a65251dd3 | |
parent | 85b7b78bbfd84e323374ebe7dbf20d5be696ac36 (diff) | |
download | leetcode-3db8c23a3d67a84980523cb06a3aa4a5febba291.tar.gz leetcode-3db8c23a3d67a84980523cb06a3aa4a5febba291.zip |
2999. count the number of powerful integers
-rw-r--r-- | count_number_powerful_integers.cpp | 41 | ||||
-rw-r--r-- | count_number_powerful_integers.py | 47 |
2 files changed, 88 insertions, 0 deletions
diff --git a/count_number_powerful_integers.cpp b/count_number_powerful_integers.cpp new file mode 100644 index 0000000..2d5981d --- /dev/null +++ b/count_number_powerful_integers.cpp @@ -0,0 +1,41 @@ +// 2999. Count the Number of Powerful Integers +#include "leetcode.h" + +/* + * you are given three integers 'start', 'finish', and 'limit'. you are also + * given a 0-indexed string 's' representing a positive integer. a positive + * integer 'x' is called powerful if it ends with 's' and each digit in 'x' is + * at most 'limit'. return the total number of powerful integers in the range + * '[start .. finish]'. a string 'x' is a suffix of a string 'y' if and only if + * 'x' is a substring of 'y' that starts from some index in 'y' and extends to + * the index 'y.length - 1'. + */ + +class Solution { +private: + long long cnt[16]; + long long get_cnt(char l, const string &n, const string &s) { + long long res = cnt[n.size() - 1], i = 0, size = n.size() - s.size(); + do + res += i == size ? n.substr(i) >= s + : cnt[n.size() - i - 1] * (min(l, n[i]) - '1' + (i > 0)); + while (i < size && n[i++] < l); + return res; + } + +public: + long long numberOfPowerfulInt(long long start, long long finish, int limit, + string s) { + for (int i = s.size(); i < 16; ++i) + cnt[i] = i == s.size() ? 1 : cnt[i - 1] * (limit + 1); + return get_cnt(limit + '1', to_string(finish), s) - + get_cnt(limit + '1', to_string(start - 1), s); + } +}; + +int main() { + Solution obj; + printf("%lld\n", obj.numberOfPowerfulInt(1, 6000, 4, "124")); // expect: 5 + printf("%lld\n", obj.numberOfPowerfulInt(15, 215, 6, "")); // expect: 2 + printf("%lld\n", obj.numberOfPowerfulInt(1000, 2000, 4, "3000")); // expect: 0 +} diff --git a/count_number_powerful_integers.py b/count_number_powerful_integers.py new file mode 100644 index 0000000..da77940 --- /dev/null +++ b/count_number_powerful_integers.py @@ -0,0 +1,47 @@ +# 2999. Count the Number of Powerful Integers + +""" +you are given three integers 'start', 'finish', and 'limit'. you are also +given a 0-indexed string 's' representing a positive integer. a positive +integer 'x' is called powerful if it ends with 's' and each digit in 'x' is +at most 'limit'. return the total number of powerful integers in the range +'[start .. finish]'. a string 'x' is a suffix of a string 'y' if and only if +'x' is a substring of 'y' that starts from some index in 'y' and extends to +the index 'y.length - 1'. +""" + + +class Solution(object): + def numberOfPowerfulInt(self, start, finish, limit, s): + """ + :type start: int + :type finish: int + :type limit: int + :type s: str + :rtype: int + """ + cnt = [0] * 16 + + def get_cnt(n, s): + res, i, size = cnt[len(n) - 1], 0, len(n) - len(s) + while True: + res += ( + n[i:] >= s + if i == size + else cnt[len(n) - i - 1] * (min(limit, int(n[i]) - 1) + (i > 0)) + ) + i += 1 + if i > size or int(n[i - 1]) > limit: + break + return res + + for i in range(len(s), 16): + cnt[i] = 1 if i == len(s) else cnt[i - 1] * (limit + 1) + return get_cnt(str(finish), s) - get_cnt(str(start - 1), s) + + +if __name__ == "__main__": + obj = Solution() + print(obj.numberOfPowerfulInt(start=1, finish=6000, limit=4, s="124")) + print(obj.numberOfPowerfulInt(start=15, finish=215, limit=6, s="10")) + print(obj.numberOfPowerfulInt(start=1000, finish=2000, limit=4, s="3000")) |