Given two strings s and t, both consisting of lowercase English letters and digits, your task is to calculate how many ways exactly one digit could be removed from one of the strings so that s is lexicographically smaller than t after the removal. Note that we are removing only a single instance of a single digit, rather than all instances (eg: removing 1 from the string a11b1c could result in a1b1c or a11bc, but not abc).
Also note that digits are considered lexicographically smaller than letters.
Example
• For s = "ab12c" and t = "1zz456", the output should be solution(s, t) = 1.
Here are all the possible removals:
o We can remove the first digit from s, obtaining "ab2c". "ab2c" > "1zz456", so we don't count this removal
o We can remove the second digit from s, obtaining "ab1c". "ab1c" > "1zz456", so we don't count this removal
o We can remove the first digit from t, obtaining "zz456". "ab12c" < "zz456", so we count this removal
o We can remove the second digit from t, obtaining "1zz56". "ab12c" > "1zz56", so we don't count this removal
o We can remove the third digit from t, obtaining "1zz46". "ab12c" > "1zz46", so we don't count this removal
o We can remove the fourth digit from t, obtaining "1zz45". "ab12c" > "1zz45", so we don't count this removal
The only valid case where s < t after removing a digit is "ab12c" < "zz456". Therefore, the answer is 1.
• For s = "ab12c" and t = "ab24z", the output should be solution(s, t) = 3.
There are 4 possible ways of removing the digit:
o "ab1c" < "ab24z"
o "ab2c" > "ab24z"
o "ab12c" < "ab4z"
o "ab12c" < "ab2z"
Three of these cases match the requirement that s < t, so the answer is 3.
Input/Output
• [execution time limit] 3 seconds (java)
• [input] string s
A string consisting of lowercase English letters and digits 0..9.
Guaranteed constraints:
1 ≤ s.length ≤ 103.
• [input] string t
A string consisting of lowercase English letters and digits 0..9.
Guaranteed constraints:
1 ≤ t.length ≤ 103.
• [output] integer
The number of ways to remove exactly one digit from one of the strings so that s is lexicographically smaller than t after the removal.
Java solution:
int solution(String s, String t) {
int count = 0;
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
String u = (i-1 >= 0 ? s.substring(0, i) : "") + (i+1 < s.length() ? s.substring(i+1, s.length()) : "");
//// System.out.println(u + " " + t);
if (lessThan(u,t)) {
count++;
}
}
}
for (int j = 0; j < t.length(); j++) {
if (t.charAt(j) >= '0' && t.charAt(j) <= '9') {
String u = (j-1 >= 0 ? t.substring(0, j) : "") + (j+1 < t.length() ? t.substring(j+1, t.length()) : "");
///// System.out.println(s + " " + u);
if (lessThan(s,u)) {
count++;
}
}
}
return count;
}
void print(String s, String t) {
List<String> r = new ArrayList<String>();
r.add(s);
r.add(t);
Collections.sort(r);
System.out.println(Arrays.toString(r.toArray()));
}
boolean lessThan(String s, String t) {
List<String> r = new ArrayList<String>();
r.add(s);
r.add(t);
Collections.sort(r);
return r.get(0).equals(s);
}
Kotlin solution:
import java.util.Collections;
fun main() {
println(solution("ab12c", "1zz456"));
}
fun solution(s: String, t: String): Int {
var count = 0;
for (i in 0..s.length-1){
if (s[i] >= '0' && s[i] <= '9') {
var u = "";
if (i-1 >= 0) {
u += s.substring(0..i-1);
}
if (i+1 < s.length) {
u += s.substring((i+1)..s.length-1);
}
println(u + " " + t);
if (lessThan(u,t)) {
count++;
}
}
}
for (j in 0..t.length-1) {
if (t[j] >= '0' && t[j] <= '9') {
var u = "";
if (j-1 >= 0) {
u += t.substring(0..j-1);
}
if (j+1 < t.length) {
u += t.substring((j+1)..t.length-1);
}
println(s + " " + u);
if (lessThan(s,u)) {
count++;
}
}
}
return count;
}
fun lessThan(s: String, t: String) : Boolean {
var r = ArrayList<String>();
r.add(s);
r.add(t);
Collections.sort(r);
return r.get(0).equals(s);
}
Test 1:
Input:
s: "ab12c"
t: "1zz456"
Output:
1
Expected Output:
1
Console Output:
ab2c 1zz456
ab1c 1zz456
ab12c zz456
ab12c 1zz56
ab12c 1zz46
ab12c 1zz45
Error Output:
Empty
Test 2:
Input:
s: "ab12c"
t: "ab24z"
Output:
3
Expected Output:
3
Console Output:
ab2c ab24z
ab1c ab24z
ab12c ab4z
ab12c ab2z
Error Output:
Empty
Test 3:
Input:
s: "96726"
t: "9z34c"
Output:
8
Expected Output:
8
Console Output:
6726 9z34c
9726 9z34c
9626 9z34c
9676 9z34c
9672 9z34c
96726 z34c
96726 9z4c
96726 9z3c
Error Output:
Empty
Test 4:
Input:
s: "4u05q"
t: "ed0r7"
Output:
4
Expected Output:
4
Console Output:
u05q ed0r7
4u5q ed0r7
4u0q ed0r7
4u05q edr7
4u05q ed0r
Error Output:
Empty
Test 5:
Input:
s: "6"
t: "h"
Output:
1
Expected Output:
1
Console Output:
h
Error Output:
Empty
Problem 2:
You are given an array of integers a, where each element a[i] represents the length of a ribbon.
Your goal is to obtain k ribbons of the same length, by cutting the ribbons into as many pieces as you want.
Your task is to calculate the maximum integer length L for which it is possible to obtain at least k ribbons of length L by cutting the given ones.
Example
• For a = [5, 2, 7, 4, 9] and k = 5, the output should be solution(a, k) = 4.
Here's a way to achieve 5 ribbons of length 4:
o Cut the ribbon of length 5 into one ribbon of length 1 (which can be discarded) and one ribbon of length 4.
o Cut the ribbon of length 7 into one ribbon of length 3 (which can be discarded) and one ribbon of length 4.
o Use the existing ribbon of length 4 (no need to cut it)
o Cut the ribbon of length 9 into two ribbons of length 4 (and one of length 1 which can be discarded)
o Discard the ribbon of length 2.
And since it wouldn't be possible to make 5 ribbons of any greater length, the answer is 4.
• For a = [1, 2, 3, 4, 9] and k = 6, the output should be solution(a, k) = 2.
Here's one way we could make 6 ribbons of length 2:
o Cut the ribbon of length 9 into four ribbons of length 2 and one ribbon of length 1 (which won't be used).
o Cut the ribbon of length 4 into two ribbons of length 2.
o Ignore all other ribbons (1, 2, and 3). Even though ribbons with lengths 2 and 3 can also be used to obtain the ribbon of length 2, we don't need more than 6 ribbons of that length.
It would technically be possible to make 6 ribbons of a length as great as 2.25, but since only integer values are allowed, the answer is 2.
Input/Output
• [execution time limit] 3 seconds (java)
• [input] array.integer a
An array of the ribbons' lengths.
Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ 109.
• [input] integer k
The number of equal-length ribbons you need to obtain. It is guaranteed that it is possible to obtain this number of ribbons from the values in a.
Guaranteed constraints:
1 ≤ k ≤ min(sum(a[i]), 109).
• [output] integer
The maximum possible length of the obtained k ribbons.
Solution 2:
Java solution:
int solution(int[] a, int k) {
var max = Arrays.stream(a).max().getAsInt();
for (int i = 1; i <= max; i++) {
int count = 0;
for (int j = 0; j < a.length; j++) {
if (a[j] >= i) {
count += a[j] / i;
}
}
if (count < k) {
return i-1;
}
}
return max;
}
Kotlin solution:
fun ribbons(a: IntArray, k: Int): Int {
var max = Arrays.stream(a).max().getAsInt();
for (i in 1..max) {
var count = 0;
for (j in 0..a.size-1) {
if (a[j] >= i) {
count += a[j] / i;
}
}
if (count < k) {
return i-1;
}
}
return max;
}
Test Case 1:
Input:
a: [5, 2, 7, 4, 9]
k: 5
Output:
4
Expected Output:
4
Console Output:
Empty
Error Output:
Empty
Test Case 2:
Input:
a: [1, 2, 3, 4, 9]
k: 6
Output:
2
Expected Output:
2
Console Output:
Empty
Error Output:
Empty
Test Case 3:
Input:
a: [1, 2, 3, 4, 9]
k: 5
Output:
3
Expected Output:
3
Console Output:
Empty
Error Output:
Empty
Test Case 4:
Input:
a: [8, 4, 2, 6, 1, 2, 1, 7]
k: 14
Output:
2
Expected Output:
2
Console Output:
Empty
Error Output:
Empty
Test Case 5:
Input:
a: [4, 8, 4, 5, 3, 7, 1, 2, 6]
k: 5
Output:
4
Expected Output:
4
Console Output:
Empty
Error Output:
Empty
No comments:
Post a Comment