leetcode

commit 650444fc9a75deeb24a95781963dc30aee38b6af
parent 1f75a5874ad6db72c5715312e9b61f403fb34767
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 22 Sep 2024 20:47:25 +0200

Daily Problem

Diffstat:
A
Problems/0440.cpp
 | 
31
+++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 32 insertions(+), 0 deletions(-)
diff --git a/Problems/0440.cpp b/Problems/0440.cpp
@@ -0,0 +1,31 @@
+class Solution {
+    static int count(int n, long p1, long p2) {
+        int steps = 0;
+        while (p1 <= n) {
+
+            steps += min((long)(n + 1), p2) - p1;
+            p1 *= 10, p2 *= 10;
+        }
+
+        return steps;
+    }
+
+  public:
+    int findKthNumber(int n, int k) const {
+        int crnt = 1;
+        k--;
+
+        while (k > 0) {
+            int step = count(n, crnt, crnt + 1);
+            if (step <= k) {
+                crnt++;
+                k -= step;
+            } else {
+                crnt *= 10;
+                k--;
+            }
+        }
+
+        return crnt;
+    }
+};
diff --git a/README.md b/README.md
@@ -334,6 +334,7 @@ for solving problems.
 |  0436  |   Medium   | [Find Right Interval](Problems/0436.cpp)                                                           |
 |  0437  |   Medium   | [Path Sum III](Problems/0437.cpp)                                                                  |
 |  0438  |   Medium   | [Find All Anagrams in a String](Problems/0438.cpp)                                                 |
+|  0440  |    Hard    | [K-th Smallest in Lexicographical Order](Problems/0440.cpp)                                        |
 |  0442  |   Medium   | [Find All Duplicates in an Array](Problems/0442.cpp)                                               |
 |  0443  |   Medium   | [String Compression](Problems/0443.cpp)                                                            |
 |  0445  |   Medium   | [Add Two Numbers II](Problems/0445.cpp)                                                            |