aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-09 20:10:30 -0600
committerJack Sangdahl <[email protected]>2025-04-09 20:11:06 -0600
commit3db8c23a3d67a84980523cb06a3aa4a5febba291 (patch)
treeaa04ebc65df7386660e63556592d104a65251dd3
parent85b7b78bbfd84e323374ebe7dbf20d5be696ac36 (diff)
downloadleetcode-3db8c23a3d67a84980523cb06a3aa4a5febba291.tar.gz
leetcode-3db8c23a3d67a84980523cb06a3aa4a5febba291.zip
2999. count the number of powerful integers
-rw-r--r--count_number_powerful_integers.cpp41
-rw-r--r--count_number_powerful_integers.py47
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"))