Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8d9deee

Browse files
authored
Added tasks 3345-3348
1 parent360f4bf commit8d9deee

File tree

12 files changed

+433
-0
lines changed

12 files changed

+433
-0
lines changed
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg3301_3400.s3345_smallest_divisible_digit_product_i;
2+
3+
// #Easy #Math #Enumeration #2024_11_13_Time_0_ms_(100.00%)_Space_41.2_MB_(29.77%)
4+
5+
publicclassSolution {
6+
publicintsmallestNumber(intn,intt) {
7+
intnum = -1;
8+
intcheck =n;
9+
while (num == -1) {
10+
intproduct =findProduct(check);
11+
if (product %t ==0) {
12+
num =check;
13+
}
14+
check +=1;
15+
}
16+
returnnum;
17+
}
18+
19+
privateintfindProduct(intcheck) {
20+
intres =1;
21+
while (check >0) {
22+
res *=check %10;
23+
check =check /10;
24+
}
25+
returnres;
26+
}
27+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
3345\. Smallest Divisible Digit Product I
2+
3+
Easy
4+
5+
You are given two integers`n` and`t`. Return the**smallest** number greater than or equal to`n` such that the**product of its digits** is divisible by`t`.
6+
7+
**Example 1:**
8+
9+
**Input:** n = 10, t = 2
10+
11+
**Output:** 10
12+
13+
**Explanation:**
14+
15+
The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition.
16+
17+
**Example 2:**
18+
19+
**Input:** n = 15, t = 3
20+
21+
**Output:** 16
22+
23+
**Explanation:**
24+
25+
The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition.
26+
27+
**Constraints:**
28+
29+
*`1 <= n <= 100`
30+
*`1 <= t <= 10`
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg3301_3400.s3346_maximum_frequency_of_an_element_after_performing_operations_i;
2+
3+
// #Medium #Array #Sorting #Binary_Search #Prefix_Sum #Sliding_Window
4+
// #2024_11_13_Time_7_ms_(96.84%)_Space_56.4_MB_(92.35%)
5+
6+
publicclassSolution {
7+
privateintgetMax(int[]nums) {
8+
intmax =nums[0];
9+
for (intnum :nums) {
10+
max =Math.max(num,max);
11+
}
12+
returnmax;
13+
}
14+
15+
publicintmaxFrequency(int[]nums,intk,intnumOperations) {
16+
intmaxNum =getMax(nums);
17+
intn =maxNum +k +2;
18+
int[]freq =newint[n];
19+
for (intnum :nums) {
20+
freq[num]++;
21+
}
22+
int[]pref =newint[n];
23+
pref[0] =freq[0];
24+
for (inti =1;i <n;i++) {
25+
pref[i] =pref[i -1] +freq[i];
26+
}
27+
intres =0;
28+
for (inti =0;i <n;i++) {
29+
intleft =Math.max(0,i -k);
30+
intright =Math.min(n -1,i +k);
31+
inttot =pref[right];
32+
if (left >0) {
33+
tot -=pref[left -1];
34+
}
35+
res =Math.max(res,freq[i] +Math.min(numOperations,tot -freq[i]));
36+
}
37+
returnres;
38+
}
39+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3346\. Maximum Frequency of an Element After Performing Operations I
2+
3+
Medium
4+
5+
You are given an integer array`nums` and two integers`k` and`numOperations`.
6+
7+
You must perform an**operation**`numOperations` times on`nums`, where in each operation you:
8+
9+
* Select an index`i` that was**not** selected in any previous operations.
10+
* Add an integer in the range`[-k, k]` to`nums[i]`.
11+
12+
Return the**maximum** possible frequency of any element in`nums` after performing the**operations**.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[1,4,5], k = 1, numOperations = 2
17+
18+
**Output:** 2
19+
20+
**Explanation:**
21+
22+
We can achieve a maximum frequency of two by:
23+
24+
* Adding 0 to`nums[1]`.`nums` becomes`[1, 4, 5]`.
25+
* Adding -1 to`nums[2]`.`nums` becomes`[1, 4, 4]`.
26+
27+
**Example 2:**
28+
29+
**Input:** nums =[5,11,20,20], k = 5, numOperations = 1
30+
31+
**Output:** 2
32+
33+
**Explanation:**
34+
35+
We can achieve a maximum frequency of two by:
36+
37+
* Adding 0 to`nums[1]`.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
42+
* <code>1 <= nums[i] <= 10<sup>5</sup></code>
43+
* <code>0 <= k <= 10<sup>5</sup></code>
44+
*`0 <= numOperations <= nums.length`
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
packageg3301_3400.s3347_maximum_frequency_of_an_element_after_performing_operations_ii;
2+
3+
// #Hard #Array #Sorting #Binary_Search #Prefix_Sum #Sliding_Window
4+
// #2024_11_13_Time_30_ms_(98.88%)_Space_56.7_MB_(93.07%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmaxFrequency(int[]nums,intk,intnumOperations) {
10+
Arrays.sort(nums);
11+
intn =nums.length;
12+
intl =0;
13+
intr =0;
14+
inti =0;
15+
intj =0;
16+
intres =0;
17+
while (i <n) {
18+
while (j <n &&nums[j] ==nums[i]) {
19+
j++;
20+
}
21+
while (l <i &&nums[i] -nums[l] >k) {
22+
l++;
23+
}
24+
while (r <n &&nums[r] -nums[i] <=k) {
25+
r++;
26+
}
27+
res =Math.max(res,Math.min(i -l +r -j,numOperations) +j -i);
28+
i =j;
29+
}
30+
i =0;
31+
j =0;
32+
while (i <n &&j <n) {
33+
while (j <n &&j -i <numOperations &&nums[j] -nums[i] <=k *2) {
34+
j++;
35+
}
36+
res =Math.max(res,j -i);
37+
i++;
38+
}
39+
returnres;
40+
}
41+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3347\. Maximum Frequency of an Element After Performing Operations II
2+
3+
Hard
4+
5+
You are given an integer array`nums` and two integers`k` and`numOperations`.
6+
7+
You must perform an**operation**`numOperations` times on`nums`, where in each operation you:
8+
9+
* Select an index`i` that was**not** selected in any previous operations.
10+
* Add an integer in the range`[-k, k]` to`nums[i]`.
11+
12+
Return the**maximum** possible frequency of any element in`nums` after performing the**operations**.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[1,4,5], k = 1, numOperations = 2
17+
18+
**Output:** 2
19+
20+
**Explanation:**
21+
22+
We can achieve a maximum frequency of two by:
23+
24+
* Adding 0 to`nums[1]`, after which`nums` becomes`[1, 4, 5]`.
25+
* Adding -1 to`nums[2]`, after which`nums` becomes`[1, 4, 4]`.
26+
27+
**Example 2:**
28+
29+
**Input:** nums =[5,11,20,20], k = 5, numOperations = 1
30+
31+
**Output:** 2
32+
33+
**Explanation:**
34+
35+
We can achieve a maximum frequency of two by:
36+
37+
* Adding 0 to`nums[1]`.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
42+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
43+
* <code>0 <= k <= 10<sup>9</sup></code>
44+
*`0 <= numOperations <= nums.length`
Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
packageg3301_3400.s3348_smallest_divisible_digit_product_ii;
2+
3+
// #Hard #String #Math #Greedy #Backtracking #Number_Theory
4+
// #2024_11_13_Time_21_ms_(100.00%)_Space_47_MB_(65.91%)
5+
6+
publicclassSolution {
7+
publicStringsmallestNumber(Stringnum,longt) {
8+
longtmp =t;
9+
for (inti =9;i >1;i--) {
10+
while (tmp %i ==0) {
11+
tmp /=i;
12+
}
13+
}
14+
if (tmp >1) {
15+
return"-1";
16+
}
17+
18+
char[]s =num.toCharArray();
19+
intn =s.length;
20+
long[]leftT =newlong[n +1];
21+
leftT[0] =t;
22+
inti0 =n -1;
23+
for (inti =0;i <n;i++) {
24+
if (s[i] =='0') {
25+
i0 =i;
26+
break;
27+
}
28+
leftT[i +1] =leftT[i] /gcd(leftT[i], (long)s[i] -'0');
29+
}
30+
if (leftT[n] ==1) {
31+
returnnum;
32+
}
33+
for (inti =i0;i >=0;i--) {
34+
while (++s[i] <='9') {
35+
longtt =leftT[i] /gcd(leftT[i], (long)s[i] -'0');
36+
for (intj =n -1;j >i;j--) {
37+
if (tt ==1) {
38+
s[j] ='1';
39+
continue;
40+
}
41+
for (intk =9;k >1;k--) {
42+
if (tt %k ==0) {
43+
s[j] = (char) ('0' +k);
44+
tt /=k;
45+
break;
46+
}
47+
}
48+
}
49+
if (tt ==1) {
50+
returnnewString(s);
51+
}
52+
}
53+
}
54+
StringBuilderans =newStringBuilder();
55+
for (inti =9;i >1;i--) {
56+
while (t %i ==0) {
57+
ans.append((char) ('0' +i));
58+
t /=i;
59+
}
60+
}
61+
while (ans.length() <=n) {
62+
ans.append('1');
63+
}
64+
returnans.reverse().toString();
65+
}
66+
67+
privatelonggcd(longa,longb) {
68+
while (a !=0) {
69+
longtmp =a;
70+
a =b %a;
71+
b =tmp;
72+
}
73+
returnb;
74+
}
75+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
3348\. Smallest Divisible Digit Product II
2+
3+
Hard
4+
5+
You are given a string`num` which represents a**positive** integer, and an integer`t`.
6+
7+
A number is called**zero-free** if_none_ of its digits are 0.
8+
9+
Return a string representing the**smallest****zero-free** number greater than or equal to`num` such that the**product of its digits** is divisible by`t`. If no such number exists, return`"-1"`.
10+
11+
**Example 1:**
12+
13+
**Input:** num = "1234", t = 256
14+
15+
**Output:** "1488"
16+
17+
**Explanation:**
18+
19+
The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256.
20+
21+
**Example 2:**
22+
23+
**Input:** num = "12355", t = 50
24+
25+
**Output:** "12355"
26+
27+
**Explanation:**
28+
29+
12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150.
30+
31+
**Example 3:**
32+
33+
**Input:** num = "11111", t = 26
34+
35+
**Output:** "-1"
36+
37+
**Explanation:**
38+
39+
No number greater than 11111 has the product of its digits divisible by 26.
40+
41+
**Constraints:**
42+
43+
* <code>2 <= num.length <= 2 * 10<sup>5</sup></code>
44+
*`num` consists only of digits in the range`['0', '9']`.
45+
*`num` does not contain leading zeros.
46+
* <code>1 <= t <= 10<sup>14</sup></code>
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3301_3400.s3345_smallest_divisible_digit_product_i;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidsmallestNumber() {
11+
assertThat(newSolution().smallestNumber(10,2),equalTo(10));
12+
}
13+
14+
@Test
15+
voidsmallestNumber2() {
16+
assertThat(newSolution().smallestNumber(15,3),equalTo(16));
17+
}
18+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3301_3400.s3346_maximum_frequency_of_an_element_after_performing_operations_i;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmaxFrequency() {
11+
assertThat(newSolution().maxFrequency(newint[] {1,4,5},1,2),equalTo(2));
12+
}
13+
14+
@Test
15+
voidmaxFrequency2() {
16+
assertThat(newSolution().maxFrequency(newint[] {5,11,20,20},5,1),equalTo(2));
17+
}
18+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp