Repository navigation
Expand file tree
/
Copy pathLeetCode2.cpp
More file actions
5436 lines (4414 loc) · 138 KB
/
Copy pathLeetCode2.cpp
File metadata and controls
5436 lines (4414 loc) · 138 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#include <iostream>
#include <vector>
#include <algorithm>
#include <typeinfo>
#include <string>
#include <cmath>
#include <numeric>
#include <iterator>
#include <list>
#include <climits>
#include <utility>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;
// LeetCode Data Structures
class ListNode {
public:
int val;
ListNode *next;
// Initialization List
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// L.C 1488, Avoid Flood in The City, Binary Search & Hashmap
vector<int> AvoidFloodInCity(vector<int> &rains) {
int size = rains.size();
vector<int> ans(size, -1);
// Storing zeros
set<int> dry;
// Storing the lake and its last position of insertion
unordered_map<int, int> lakes;
for(int i=0; i<size; i++) {
// Dry Day
if(rains[i] == 0) {
dry.insert(i);
}
else {
auto it = lakes.find(rains[i]);
// If lake is already filled
if(it != lakes.end()) {
int prev = it->second;
// Zero after last position of insertion
auto lb = dry.lower_bound(prev);
// If there is a zero, updation
if(lb != dry.end()) {
// Drying the lake
ans[*lb] = rains[i];
// Erasing zeros
dry.erase(lb);
// Updation to last position of insertion
lakes[it->first] = i;
}
// If there is no day to dry the lake
else {
return {};
}
}
// Lake isnt filled
else {
lakes[rains[i]] = i;
}
}
}
// Can dry any lake on days where no work is done (taking 5), wont impact the answer
while(!dry.empty()) {
ans[*dry.begin()] = 5;
dry.erase(dry.begin());
}
return ans;
}
// L.C 2300, Successful Pairs of Spells and Potions, Binary Search
vector<int> SuccessfulPairsSpellsAndPotions(vector<int> &spells, vector<int> &potions, long long success) {
int size = spells.size();
// Intialise with 0 so if lb == potions.end(), no need to update ans
vector<int> ans(size, 0);
// LogN T.C lower_bound
sort(potions.begin(), potions.end());
for(int i=0; i<size; i++) {
int div = success/spells[i];
auto lb = lower_bound(potions.begin(), potions.end(), div);
// Mod range, if success == 7, and spells[i] is 2, div is 3(int) & (3.5)float
// So, potions would satisfy from 4 not from 3
while(lb != potions.end() && (1LL*spells[i]*(*lb)) < success ) {
lb++;
}
// Non-zero condition
if(lb != potions.end()) {
ans[i] = distance(lb, potions.end());
}
}
return ans;
}
// L.C 1695, Maximum Erasure Value, Sliding Window
int MaximumUniqueSubarray(vector<int> &nums) {
int l=0;
int r=0;
int size = nums.size();
int count = 0;
int maxi = 0;
unordered_map<int, int> lastOccur;
while(r < size) {
// Already exists
if(lastOccur.count(nums[r])) {
// In-between L&R
if(l <= lastOccur[nums[r]]) {
// Total maxi
maxi = max(maxi, count);
int removedCount = 0;
while(l != lastOccur[nums[r]]+1) {
removedCount += nums[l];
l++;
}
// Final calculation
count -= removedCount;
}
}
lastOccur[nums[r]] = r;
count += nums[r];
r++;
}
// After last value
maxi = max(maxi, count);
return maxi;
}
// L.C 3494, Find the Minimum Amount of Time to Brew Potions, 1D-DP (Tab)
long long MinTimeToBrewPotion(vector<int> &skill, vector<int> &mana) {
int n = skill.size();
int m = mana.size();
// n+1 because Start-Time is also considered & at dp[0]
vector<long long> dp(n+1, 0);
for(int j=0; j<m; j++) {
// Max-Time se aage badhta jaega
for(int i=0; i<n; i++) {
dp[i+1] = max(dp[i+1], dp[i]) + skill[i]*mana[j];
}
// Phir uss Max-Time se piche aajao
for(int i=n-1; i>=0; i--) {
dp[i] = dp[i+1] - skill[i]*mana[j];
}
}
return dp[n];
}
// L.C 3147, Taking Maximum Energy From the Mystic Dungeon, 1D-DP (Tab)
int MaximumEnergyDungeon(vector<int> &energy, int k) {
int size = energy.size();
vector<int> dp(size, 0);
int maxi = INT_MIN;
// Calculate sum for first k elements
for(int i=0; i<k; i++) {
for(int j=i; j<size; j += k) {
dp[i] += energy[j];
}
maxi = max(maxi, dp[i]);
}
// Remove the i-kth element from them
for(int i=k; i<size; i++) {
dp[i] = dp[i-k] - energy[i-k];
maxi = max(maxi, dp[i]);
}
return maxi;
}
// L.C 3186, Maximum Total Damage With Spell Casting, 1D-DP (Memo)
long long MaxTotalDamageSpellMemo(int i, vector<pair<int,long long>> &powerUniqSum, vector<long long> &dp) {
// Base Case
if(i >= powerUniqSum.size()) {
return 0;
}
if(dp[i] != -1) {
return dp[i];
}
int j = i+1;
while(j<powerUniqSum.size() && powerUniqSum[j].first <= powerUniqSum[i].first+2) {
j++;
}
// Consider
long long opt1 = powerUniqSum[i].second + MaxTotalDamageSpellMemo(j, powerUniqSum, dp);
// Skip
long long opt2 = 0 + MaxTotalDamageSpellMemo(i+1, powerUniqSum, dp);
dp[i] = max(opt1, opt2);
return dp[i];
}
long long MaxTotalDamageSpell(vector<int> &power) {
long long maxi = 0;
unordered_map<int, long long> freqSum;
vector<pair<int, long long>> powerUniqSum;
// Same no. sum
for(int ch: power) {
freqSum[ch] += ch;
}
// New Vector to be passed
for(auto ch: freqSum) {
powerUniqSum.push_back( {ch.first, ch.second} );
}
int size = powerUniqSum.size();
sort(powerUniqSum.begin(), powerUniqSum.end());
vector<long long> dp(size, -1);
return MaxTotalDamageSpellMemo(0, powerUniqSum, dp);
}
// Biweekly 167
// Easy, L.C 3707, Equal Score Substrings, Prefix-Sum
bool ScoreBalanceString(string s) {
int size = s.length();
int tSum = 0;
int lSum = 0;
// Total sum
for(char ch: s) {
tSum += ch-'a'+1;
}
// rSum = tSum - lSum
for(char ch: s) {
lSum += ch-'a'+1;
tSum -= ch-'a'+1;
// Point where string divides
if(lSum == tSum) {
return true;
}
}
return false;
}
// Med 1, L.C 3708, Longest Fibonacci Subarray, Sliding Window
int LongestFibSubarray(vector<int> &nums) {
// Minimum Fib, given in question
int maxLength = 2;
int l = 0;
int r = 1;
while(r < nums.size()) {
// Fib first window
if( r+1 < nums.size() && nums[l] + nums[r] == nums[r+1] ) {
// Fib window stretch
while(r+1 < nums.size() && (nums[r-1] + nums[r] == nums[r+1]) ) {
r++;
}
// Length
maxLength = max(maxLength, r-l+1);
l=r;
r++;
}
else {
l++;
r++;
}
}
return maxLength;
}
// Med 2, L.C 3709, Design Exam Scores Tracker, System Design, Prefix-Sum
class ExamTracker {
public:
unordered_map<int, int> timeAndScore;
long long sum = 0;
map<int, long long> timeAndSum;
ExamTracker() {
// First entry se lower wala lower_bound yaha aajaenge
this->timeAndScore[0] = 0;
this->timeAndSum[0] = 0;
}
void record(int time, int score) {
timeAndScore[time] = score;
sum += score;
// Store total score till time
timeAndSum[time] = sum;
}
long long totalScore(int startTime, int endTime) {
long long score = 0;
auto itStart = timeAndSum.lower_bound(startTime);
auto itEnd = timeAndSum.lower_bound(endTime);
// Last Entry ke aage aaya
if(endTime < itEnd->first) {
itEnd--;
}
// Inbetween wale haat aajaenge
if(itEnd->first < itStart->first) {
return 0;
}
// Same Time
if(itStart->first == itEnd->first) {
return timeAndScore[itEnd->first];
}
// General Case
score = itEnd->second - itStart->second + timeAndScore[itStart->first];
return score;
}
};
// Hard, L.C 3710, Maximum Partition Factor
// Is Bipartitte
bool MaxPartitionFactorIsBipartite(int parent, int childColour, int parentColour, int &distance, vector<int> &visited, vector<vector<int>> &points) {
// Marking
visited[parent] = parentColour;
int size = points.size();
for(int i=0; i<size; i++) {
// Parent itself or iI neighbour has the same colour as parent or Greater distance than mid
if( i == parent || visited[i] == childColour || (abs(points[parent][0] - points[i][0]) + abs(points[parent][1] - points[i][1])) >= distance ) {
continue;
}
// Already Visited
else if(visited[i] == parentColour) {
return false;
}
// Recursion call
if( !MaxPartitionFactorIsBipartite(i, parentColour, childColour, distance, visited, points) ) {
return false;
}
}
return true;
}
// Checker for Bipartite
bool MaxPartitionFactorCheckForBipartite(int &distance, vector<vector<int>> &points) {
int n = points.size();
// For Bipartite
vector<int> visited(n, -1);
for(int i=0; i<n; i++) {
// Not visited
if(visited[i] == -1) {
if( !MaxPartitionFactorIsBipartite(i, 0, 1, distance, visited, points) ) {
return false;
}
}
}
return true;
}
int MaxPartitionFactor(vector<vector<int>> &points) {
int size = points.size();
// edge Case
if(size == 2) {
return 0;
}
int start = 0;
int end = 1e9;
int ans = -1e9;
// Binary search on answer
while(start <= end) {
int mid = start + ((end-start) / 2);
if( MaxPartitionFactorCheckForBipartite(mid, points) ) {
ans = max(ans, mid);
start = mid + 1;
}
else {
end = mid - 1;
}
}
return ans;
}
// Weekly 471
// Easy, L.C 3712, Sum of Elements With Frequency Divisible by K, Hashmap
int SumDivisibleByK(vector<int> &nums, int k) {
int count = 0;
unordered_map<int, int> freq;
for(int ch: nums) {
freq[ch]++;
}
for(auto &ch: freq) {
if(ch.second % k == 0) {
int f = ch.second;
while(f != 0) {
count += ch.first;
f--;
}
}
}
return count;
}
// Med 1, L.C 3713, Longest Balanced Substring I, String, Brute force due to constraints
int LongestBalancedSubStrFreq(string s) {
int maxLength = 0;
int size= s.length();
// All Substrings, Brute force due to constraints
for(int i=0; i<size; i++) {
vector<int> freq(26, 0);
for(int j=i; j<size; j++) {
int ch = s[j]-'a';
freq[ch]++;
bool target = true;
int count = 0;
// Frequency Matching
for(int k=0; k<26; k++) {
if(freq[k] != 0) {
count++;
// Frequency doesnt match
if(freq[ch] != freq[k]) {
target = false;
}
}
}
// Updation
if(target) {
maxLength = max(maxLength, count*freq[ch]);
}
}
}
return maxLength;
}
// Med 2, L.C 3714, Longest Balanced Substring II, SubArray Hashmap Sum, Prefix-Sum using Hashmap
// Largest subarray sum = 0 with Hashmap technique
void Distict2SubStrWithSumZero(string &s, char x, char y, int &maxLength) {
// x == 1 && y == -1
int size = s.length();
int counter = 0;
unordered_map<int, int> sumAndIndex;
sumAndIndex[0] = -1;
for(int i=0; i<size; i++) {
if(s[i] == x) {
counter++;
}
else if(s[i] == y) {
counter--;
}
else {
sumAndIndex.clear();
sumAndIndex[0] = i;
counter = 0;
}
// Searching in hashmap
if(sumAndIndex.count(counter)) {
maxLength = max(maxLength, i-sumAndIndex[counter]);
}
else {
sumAndIndex[counter] = i;
}
}
return;
}
// Largest subarray with same frequency for 3 characters using Hashmap technique
void Distict3SubStrWithSumZero(string &s, int &maxLength) {
int size = s.length();
// Freq[a] - Freq[b]
int countAB = 0;
// Freq[a] - Freq[c]
int countAC = 0;
// Initialization
map<pair<int, int>, int> ABandAC;
ABandAC[ {0,0} ] = -1;
for(int i=0; i<size; i++) {
if(s[i] == 'a') {
countAB++;
countAC++;
}
else if(s[i] == 'b') {
countAB--;
}
else {
countAC--;
}
// Searching in hashmap
if( ABandAC.count({countAB, countAC}) ) {
maxLength = max(maxLength, i - ABandAC[{countAB, countAC}]);
}
else {
ABandAC[{countAB, countAC}] = i;
}
}
return;
}
int LongestBalancedSubStrFreq3Chars(string s) {
int maxLength = 1;
int length = 1;
int size = s.length();
// 1 Char at a time [a/b/c]
for(int i=1; i<size; i++) {
if(s[i] == s[i-1]) {
length++;
}
else {
maxLength = max(maxLength, length);
length = 1;
}
}
// If it isnt updated till last
maxLength = max(maxLength, length);
// 2 Char at a time [ab/bc/ca]
Distict2SubStrWithSumZero(s, 'a', 'b', maxLength);
Distict2SubStrWithSumZero(s, 'c', 'b', maxLength);
Distict2SubStrWithSumZero(s, 'a', 'c', maxLength);
// 3 Char at a time [abc]
// We want freq[a] == freq[b] == freq[c]
// Freq[a] - Freq[b] == Freq[a] - Freq[c]
Distict3SubStrWithSumZero(s, maxLength);
return maxLength;
}
// Hard L.C 3715, Sum of Perfect Square Ancestors, Tree(Graph Styled, No visited required), BackTrack, Pre-computation & DFS, Square Number Properties
// Precomputing smallest prime factor
void SumOfAncestorsPrecomputeSPF(int maxi, vector<int> &spf) {
// For 1
spf[1] = 1;
// Sieve styled array
for(int i=2; i <= maxi; i++) {
if(spf[i] != -1) {
continue;
}
// Marking spf
spf[i] = i;
// j greater than 1e5
if(1LL*i*i > 1e5) {
continue;
}
for(int j = i*i; j <= maxi; j += i) {
// Like 6 will be overriden by 3, while 2 already exists
if(spf[j] == -1) {
spf[j] = i;
}
}
}
return;
}
// DFS for tree
void SumOfAncestorsDFS(int curr, int parent, long long &ans, vector<int> &finalVal, unordered_map<int, int> &freq, unordered_map<int, vector<int>> &adjList) {
// Adding ancestor with whom it can multiply
freq[finalVal[curr]]++;
for(int &nbr: adjList[curr]) {
if(nbr == parent) {
continue;
}
// Nbr ki final value kitni baar occur ho rahi hai
ans += freq[finalVal[nbr]];
// Recursion Call
SumOfAncestorsDFS(nbr, curr, ans, finalVal, freq, adjList);
}
// BackTrack
freq[finalVal[curr]]--;
return;
}
long long SumOfAncestors(int n, vector<vector<int>> &edges, vector<int> &nums) {
long long ans = 0;
// Max value & Precomputing spf
int maxi = *( max_element(nums.begin(), nums.end()) );
vector<int> spf(maxi + 1, -1);
SumOfAncestorsPrecomputeSPF(maxi, spf);
// Removing even powers from nums
// Using nums as finalVal
for(int &i: nums) {
int val = i;
int finalVal = 1;
while(val != 1) {
int count = 0;
int factor = spf[val];
while(val % factor == 0) {
count++;
val /= factor;
}
// Odd should be added like 24 => (2^3 * 3) -> 2 will be added first then 3
if(count&1) {
finalVal *= factor;
}
}
i = finalVal;
}
// Undirected graph/tree
unordered_map<int, vector<int>> adjList;
for(vector<int> &e: edges) {
adjList[e[0]].push_back(e[1]);
adjList[e[1]].push_back(e[0]);
}
// Frequency of ancestors of finalVal after removing even powers from num
unordered_map<int, int> freq;
// DFS
SumOfAncestorsDFS(0, -1, ans, nums, freq, adjList);
return ans;
}
// L.C 2273, Find Resultant Array After Removing Anagrams, Iterators
vector<string> RemoveAdjacentAnagrams(vector<string> &words) {
auto curr = words.begin();
auto next = words.begin() + 1;
while(next != words.end()) {
// Freq mapping for word[i]
vector<int> freq1(26, 0);
for(char ch: *curr) {
freq1[ch-'a']++;
}
// Freq mapping for word[i+1]
vector<int> freq2(26, 0);
for(char ch: *next) {
freq2[ch-'a']++;
}
// Same Frequency
if(freq1 == freq2) {
// Assignment is important, if we do words.erase(next), next become invlid
// Assignment maps it to the element next to it in array
next = words.erase(next);
}
else {
curr++;
next++;
}
}
return words;
}
// L.C 3349, Adjacent Increasing Subarrays Detection I, Sliding Window
bool HasAdjacentIncSubarrays1(vector<int> &nums, int k) {
bool inc1 = false;
bool inc2 = false;
int l=0;
int r=0;
int i=0;
int lastInc1 = 0;
int size = nums.size();
// Is always a sub-array
if(k == 1) {
return true;
}
while(i < size) {
// Match Found
if(i+1 < size && nums[i] < nums[i+1]) {
while(i+1 < size && nums[i] < nums[i+1]) {
i++;
}
// For length >= k
r=i;
// All increasing array such that its size >= 2*k
if(r-l+1 >= 2*k && !inc1) {
return true;
}
// First array found
else if(r-l+1 >= k && !inc1) {
i++;
inc1 = true;
}
// Second array found i.e adjacent
else if(r-l+1 >= k && inc1) {
return true;
}
// Next length
l=i;
}
// Marks first array as false;
else {
inc1 = false;
i++;
l=i;
r=i;
}
}
return false;
}
// L.C 3350, Adjacent Increasing Subarrays Detection II, Sliding Window
int HasAdjacentIncSubarrays2(vector<int> &nums) {
// Seq contains starting & ending point
vector<pair<int, int>> seq;
int maxi = 0;
int l=0;
int r=0;
int size = nums.size();
while(r < size) {
// Size >= 2 elements only
if(r+1 < size && nums[r] < nums[r+1]) {
while(r+1 < size && nums[r] < nums[r+1]) {
r++;
}
seq.push_back( {l,r} );
}
// Updation
r++;
l=r;
}
// Updating Size
size = seq.size();
// No >2 elements available
if(size == 0) {
return 1;
}
for(int i=0; i<size; i++) {
// Odd or even => 5 => 2,2 adjacent elements, Half length always
int len1 = seq[i].second - seq[i].first + 1;
maxi = max(maxi, len1/2);
// If sequence is adjacent, i.e {l1, r} && {r+1, r2}
if(i+1 < size && seq[i].second + 1 == seq[i+1].first) {
int len2 = seq[i+1].second - seq[i+1].first + 1;
// Min of both length
maxi = max(maxi, min(len1, len2));
}
}
return maxi;
}
// L.C 2598, Smallest Missing Non-negative Integer After Operations, Mod Operation
int FindSmallestMutuallyExclusive(vector<int> &nums, int value) {
// Frequency Count
// If value = 5, and array contains 1->7 then mutually exclusive is 8
// If we mod other numbers can be made using +value
vector<int> mex(value, 0);
// Operation for [0, value-1] range
for(int ch: nums) {
// Especially for (-1 to -value+1) values
if(ch < 0) {
ch = (ch % value) + value;
}
ch %= value;
mex[ch]++;
}
// Finding mex
int i = 0;
while(mex[i % value] != 0) {
mex[i % value]--;
i++;
}
return i;
}
// L.C 3397, Maximum Number of Distinct Elements After Operations, Greedy, Always check for return as arr or count, Sorting
// In count modifying everything works as we only need count, no need to preverse arrays state
int MaxDistinctElementsKRange(vector<int> &nums, int k) {
int count = 0;
int prev = INT_MIN;
sort(nums.begin(), nums.end());
// Convert all the number no matter what we only need count
for(int ch: nums) {
int low = ch-k;
int high = ch+k;
// Increment by 1 as to not encounter same no. Eg.: 4,4,4,4
int curr = prev+1;
// Gap between 2 number
if(curr < low) {
curr = low;
}
// Storing state in prev
if(curr <= high) {
prev = curr;
count++;
}
}
return count;
}
// L.C 2011, Final Value of Variable After Performing Operations
int FinalValueAfterOperationsIncDec(vector<string> &operations) {
int ans = 0;
for(string ch: operations) {
// X++ && ++X
if(ch[1] == '+') {
ans++;
}
// X-- && --X
else {
ans--;
}
}
return ans;
}
// L.C 3461, Check If Digits Are Equal in String After Operations I
bool HasSameDigitsIn0And1Pos(string s) {
while(s.size() > 2) {
string temp = "";
int size = s.size();
// Addition
for(int i=0; i<size-1; i++) {
int ch = ( (s[i] - '0') + (s[i+1] - '0') ) % 10;
temp += ch;
}
// Updation
s = temp;
}
return (s[0] == s[1]) ? true : false;
}
// L.C 1716, Calculate Money in Leetcode Bank
int TotalMoneyLCBank(int n) {
int count = 0;
int prev = 1;
int days = 0;
int total = 0;
while(n > 0) {
if(days == 7) {
prev++;
count = prev;
days = 1;
}
else {
count++;
days++;
}
total += count;
n--;
}
return total;
}
// L.C 2048, Next Greater Numerically Balanced Number, Prefix-Sum & next_permutation
void NextBeautifulNumberBalanced(int digit, string str, set<string> &precomp) {
// Base Case
if(str.size() > 7 || digit > 7) {
return;
}
if(str.size() > 0) {
precomp.insert(str);
}
// Adding n, n times in str
// temp so that their is no BackTrack Loop for n
string temp = str;
// Balanced
for(int i=1; i<=digit; i++) {
temp += (digit + '0');
}
// Consider the digit
NextBeautifulNumberBalanced(digit+1, temp, precomp);
// Skip the digit
NextBeautifulNumberBalanced(digit+1, str, precomp);
return;
}
void NextBeautifulNumberPrecompute(set<int> &balanced) {
// String so iteration is easy
set<string> precomp;
// Will always produce balanced outcomes
NextBeautifulNumberBalanced(1, "", precomp);
for(string s: precomp) {
do {
balanced.insert( stoi(s) );
} while( next_permutation(s.begin(), s.end()) );
}
return;
}
int NextBeautifulNumber(int n) {
set<int> balanced;
NextBeautifulNumberPrecompute(balanced);
auto it = balanced.upper_bound(n);
return *it;
}
// L.C 1625, Lexicographically Smallest String After Applying Operations, Brute Force, Memoization & Stack
void FindLexSmallestStringOpsM1(string &s, int &a, int &b, set<string> &uniq) {
// Base Case
if(uniq.count(s)) {
return;
}
// Processing
uniq.insert(s);
string og = s;
// Rotation && Recursion call
rotate(s.begin(), s.begin()+b, s.end());
FindLexSmallestStringOpsM1(s, a, b, uniq);