aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-21 21:44:03 -0600
committerJack Sangdahl <[email protected]>2024-09-21 21:44:03 -0600
commitb4a3151742e580f176f60af0815e95fa3066a5f1 (patch)
tree318d8875d89037c6e6a24547c1fe066685970fb3
parente1681d1ad79dd6a2961fe04d24c1ed2152da161a (diff)
downloadleetcode-b4a3151742e580f176f60af0815e95fa3066a5f1.tar.gz
leetcode-b4a3151742e580f176f60af0815e95fa3066a5f1.zip
440. kth smallest in lexicographical order
-rw-r--r--kth_smallest_lexicographical.c41
-rw-r--r--kth_smallest_lexicographical.cpp48
-rw-r--r--kth_smallest_lexicographical.py36
3 files changed, 74 insertions, 51 deletions
diff --git a/kth_smallest_lexicographical.c b/kth_smallest_lexicographical.c
index 85551db..3567a1f 100644
--- a/kth_smallest_lexicographical.c
+++ b/kth_smallest_lexicographical.c
@@ -1,34 +1,33 @@
// 440. K-th Smallest in Lexicographical Order
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
// given two integers 'n' and 'k', return the k'th lexicographically smallest
// integer
-int count_prefix(int n, long long prefix) {
- long long offset = 10, target = n;
- int total = 0;
- for (int i = 1; i <= 9; i++) {
- long long min = prefix * offset;
- long long max = min + offset - 1;
- if (target < min)
- break;
- total += fmin(target, max) - min + 1;
+long long count_step(long long prefix, long long n) {
+ long long curr = prefix, next = prefix + 1, steps = 0;
+ while (curr <= n) {
+ steps += (next <= n) ? next - curr : n - curr + 1;
+ curr *= 10;
+ next *= 10;
}
- return total + 1;
+ return steps;
}
int findKthNumber(int n, int k) {
- int prefix = 0;
- if (k)
- for (int i = !prefix ? 1 : 0; i <= 9; i++) {
- int prefix_cnt = count_prefix(n, 10 * prefix + i);
- if (k <= prefix_cnt)
- return findKthNumber(n, k - 1);
- k -= prefix_cnt;
+ int curr = 1;
+ k--;
+ while (k) {
+ long long steps = count_step(curr, n);
+ if (steps <= k) {
+ curr++;
+ k -= steps;
+ } else {
+ curr *= 10;
+ k--;
}
- return prefix;
+ }
+ return curr;
}
int main() {
diff --git a/kth_smallest_lexicographical.cpp b/kth_smallest_lexicographical.cpp
index 1e292ec..71478e9 100644
--- a/kth_smallest_lexicographical.cpp
+++ b/kth_smallest_lexicographical.cpp
@@ -1,43 +1,31 @@
+// 440. K-th Smallest in Lexicographical Order
#include "leetcode.h"
+// given two integers 'n' and 'k', return the k'th lexicographically smallest
+// integer
class Soltuion {
public:
int findKthNumber(int n, int k) {
- int ans = 0, rankNum = 0, next = 0, rankNext = 0;
- while (rankNum != k) {
- int lower = ans ? 0 : 1, upper = 9;
- while (lower < upper) {
- auto mid = (lower + upper + 1) / 2;
- next = ans * 10 + mid;
- rankNext = rank(next, n);
+ int curr = 1;
+ for (--k; k > 0;) {
+ int cnt = 0;
+ for (long long first = static_cast<long long>(curr), last = first + 1;
+ first <= n; first *= 10, last *= 10)
+ cnt += static_cast<int>((min(n + 1LL, last) - first));
+ if (k >= cnt) {
+ ++curr;
+ k -= cnt;
+ } else {
+ curr *= 10;
+ --k;
}
- ans *= 10, ans += lower;
- rankNum = (ans == next ? rankNext : rank(ans, n));
}
- return ans;
- }
-
-private:
- static int rank(int prefix, int maxVal) {
- int ret = 1, num = 0;
- for (int i = prefix; i; i /= 10, ++num)
- for (int j = 1; j <= i % 10; ++j)
- ret += numPrefixes(i - j, maxVal);
- ret += num - 1;
- return ret;
- }
- static int numPrefixes(int prefix, int maxVal) {
- if (prefix == 0)
- return 0;
- int ret = 0;
- unsigned long long ull = 1;
- for (unsigned long long val = prefix; val <= maxVal; ull *= 10, val *= 10)
- ret += min(ull, maxVal - val + 1);
- return ret;
+ return curr;
}
};
int main() {
Soltuion obj;
- cout << obj.findKthNumber(13, 2);
+ printf("%d\n", obj.findKthNumber(13, 2)); // expect: 10
+ printf("%d\n", obj.findKthNumber(1, 1)); // expect: 1
}
diff --git a/kth_smallest_lexicographical.py b/kth_smallest_lexicographical.py
new file mode 100644
index 0000000..8f56678
--- /dev/null
+++ b/kth_smallest_lexicographical.py
@@ -0,0 +1,36 @@
+# 440. K-th Smallest in Lexicographical Order
+
+"""
+given two integers 'n' and 'k', return the k'th lexicographically smallest
+integer
+"""
+
+
+class Solution(object):
+ def findKthNumber(self, n, k):
+ """
+ :type n: int
+ :type k: int
+ :rtype: int
+ """
+ curr = 1
+ k -= 1
+ while k > 0:
+ cnt = 0
+ interval = [curr, curr + 1]
+ while interval[0] <= n:
+ cnt += min(n + 1, interval[1]) - interval[0]
+ interval = [10 * interval[0], 10 * interval[1]]
+ if k >= cnt:
+ curr += 1
+ k -= cnt
+ else:
+ curr *= 10
+ k -= 1
+ return curr
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findKthNumber(13, 2))
+ print(obj.findKthNumber(1, 1))