# Cutting Edges ## Solution 1: Nested Loop with Divisibility Check ### Intuition - The problem asks us to partition a string of digits into the maximum number of segments where each segment represents a number divisible by 3. - A number is divisible by 3 if and only if the sum of its digits is divisible by 3. - The simplest approach is to try every possible starting position for a segment and greedily find the shortest valid segment, because taking a shorter valid segment leaves more digits for future segments. - Leading zeroes are only allowed if the entire segment is just "0", so we must check this condition before accepting any segment. ### Approach - Start from the beginning of the string and try to find the shortest valid segment starting at that position. - For each potential segment, check if it has no leading zeroes and if its digit sum is divisible by 3. - If a valid segment is found, increment the count and move the start position to right after this segment. - If no valid segment can be formed from the current position, return 0. - Repeat until the entire string is processed. ### Pseudocode ```pseudocode function maxContainers(S) { n = length of S pos = 0 count = 0 while pos < n { found = false for end = pos to n - 1 { if S[pos] == '0' and end > pos { continue } digitSum = 0 for i = pos to end { digitSum = digitSum + (S[i] - '0') } if digitSum % 3 == 0 { count = count + 1 pos = end + 1 found = true break } } if found == false { return 0 } } return count } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int maxContainers(string S) { int n = S.length(); int pos = 0; int count = 0; while (pos < n) { bool found = false; for (int end = pos; end < n; end++) { if (S[pos] == '0' && end > pos) { continue; } int digitSum = 0; for (int i = pos; i <= end; i++) { digitSum += (S[i] - '0'); } if (digitSum % 3 == 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } }; ``` **Python** ```python class solution: def maxContainers(self, S): n = len(S) pos = 0 count = 0 while pos < n: found = False for end in range(pos, n): # Check for leading zeroes if S[pos] == '0' and end > pos: continue digitSum = sum(int(S[i]) for i in range(pos, end + 1)) if digitSum % 3 == 0: count += 1 pos = end + 1 found = True break if not found: return 0 return count ``` **Java** ```java import java.util.*; class Solution { public int maxContainers(String S) { int n = S.length(); int pos = 0; int count = 0; while (pos < n) { boolean found = false; for (int end = pos; end < n; end++) { if (S.charAt(pos) == '0' && end > pos) { continue; } int digitSum = 0; for (int i = pos; i <= end; i++) { digitSum += (S.charAt(i) - '0'); } if (digitSum % 3 == 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } } ``` **JavaScript** ```javascript class Solution { static maxContainers(S) { let n = S.length; let pos = 0; let count = 0; while (pos < n) { let found = false; for (let end = pos; end < n; end++) { if (S[pos] === '0' && end > pos) { continue; } let digitSum = 0; for (let i = pos; i <= end; i++) { digitSum += parseInt(S[i]); } if (digitSum % 3 === 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n³)` - The outer while loop runs at most `n` times. - The middle for loop examines each end point. - The inner for loop computes digit sum. - Overall cubic. - **Space Complexity:** `O(1)` --- ## Solution 2: Greedy with Running Digit Sum ### Intuition - Recalculating the digit sum from scratch for each potential segment is wasteful. - We can maintain a running sum as we extend each potential segment, adding one digit at a time. - A greedy strategy works here: finding the shortest valid segment at each position always leads to an optimal solution because it maximizes the remaining digits for future segments. - The leading zero check remains essential—a segment starting with '0' can only be valid if it's exactly "0". ### Approach - Iterate through the string while maintaining a running digit sum. - When the current digit is '0', check if we can form the valid segment "0" immediately. - For non-zero starting digits, extend the segment while accumulating the sum. - As soon as the sum becomes divisible by 3, we've found our shortest valid segment. - If we exhaust all digits without finding a valid segment, return 0. ### Pseudocode ```pseudocode function maxContainers(S) { n = length of S pos = 0 count = 0 while pos < n { if S[pos] == '0' { count = count + 1 pos = pos + 1 continue } digitSum = 0 found = false for end = pos to n - 1 { digitSum = digitSum + (S[end] - '0') if digitSum % 3 == 0 { count = count + 1 pos = end + 1 found = true break } } if found == false { return 0 } } return count } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int maxContainers(string S) { int n = S.length(); int pos = 0; int count = 0; while (pos < n) { if (S[pos] == '0') { count++; pos++; continue; } int digitSum = 0; bool found = false; for (int end = pos; end < n; end++) { digitSum += (S[end] - '0'); if (digitSum % 3 == 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } }; ``` **Python** ```python class solution: def maxContainers(self, S): n = len(S) pos = 0 count = 0 while pos < n: if S[pos] == '0': count += 1 pos += 1 continue digitSum = 0 found = False for end in range(pos, n): digitSum += int(S[end]) if digitSum % 3 == 0: count += 1 pos = end + 1 found = True break if not found: return 0 return count ``` **Java** ```java import java.util.*; class Solution { public int maxContainers(String S) { int n = S.length(); int pos = 0; int count = 0; while (pos < n) { if (S.charAt(pos) == '0') { count++; pos++; continue; } int digitSum = 0; boolean found = false; for (int end = pos; end < n; end++) { digitSum += (S.charAt(end) - '0'); if (digitSum % 3 == 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } } ``` **JavaScript** ```javascript class Solution { static maxContainers(S) { let n = S.length; let pos = 0; let count = 0; while (pos < n) { if (S[pos] === '0') { count++; pos++; continue; } let digitSum = 0; let found = false; for (let end = pos; end < n; end++) { digitSum += parseInt(S[end]); if (digitSum % 3 === 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n²)` - The outer while loop processes each character once. - The inner for loop may scan remaining characters. - Worst-case quadratic. - **Space Complexity:** `O(1)` --- ## Solution 3: Optimized Greedy with Modulo Tracking ### Intuition - A key mathematical insight is that the digit sum only has three relevant states: modulo 0, 1, or 2. - A segment is valid when its accumulated sum modulo 3 equals 0. - If we track only the modulo value instead of the full sum, we ensure we never miss a valid segment. - For non-zero starting digits, the shortest valid segment is found when the running modulo becomes 0 (for the first time in that segment). - Single '0' digits are always valid and handled separately. ### Approach - Process the string left to right with a greedy strategy. - When encountering '0', immediately count it as a valid segment. - For non-zero digits, track the running modulo 3 of the digit sum. - The first time the modulo becomes 0 marks the shortest valid segment. - Single-digit segments like 3, 6, 9 are caught immediately; longer segments are formed only when necessary. - This approach guarantees optimal partition because taking the earliest valid segment leaves maximum digits for remaining segments. ### Pseudocode ```pseudocode function maxContainers(S) { n = length of S pos = 0 count = 0 while pos < n { if S[pos] == '0' { count = count + 1 pos = pos + 1 continue } modSum = 0 found = false for end = pos to n - 1 { modSum = (modSum + (S[end] - '0')) % 3 if modSum == 0 { count = count + 1 pos = end + 1 found = true break } } if found == false { return 0 } } return count } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int maxContainers(string S) { int n = S.length(); int pos = 0; int count = 0; while (pos < n) { if (S[pos] == '0') { count++; pos++; continue; } int modSum = 0; bool found = false; for (int end = pos; end < n; end++) { modSum = (modSum + (S[end] - '0')) % 3; if (modSum == 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } }; ``` **Python** ```python class solution: def maxContainers(self, S): n = len(S) pos = 0 count = 0 while pos < n: if S[pos] == '0': count += 1 pos += 1 continue modSum = 0 found = False for end in range(pos, n): modSum = (modSum + int(S[end])) % 3 if modSum == 0: count += 1 pos = end + 1 found = True break if not found: return 0 return count ``` **Java** ```java import java.util.*; class Solution { public int maxContainers(String S) { int n = S.length(); int pos = 0; int count = 0; while (pos < n) { if (S.charAt(pos) == '0') { count++; pos++; continue; } int modSum = 0; boolean found = false; for (int end = pos; end < n; end++) { modSum = (modSum + (S.charAt(end) - '0')) % 3; if (modSum == 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } } ``` **JavaScript** ```javascript class Solution { static maxContainers(S) { let n = S.length; let pos = 0; let count = 0; while (pos < n) { if (S[pos] === '0') { count++; pos++; continue; } let modSum = 0; let found = false; for (let end = pos; end < n; end++) { modSum = (modSum + parseInt(S[end])) % 3; if (modSum === 0) { count++; pos = end + 1; found = true; break; } } if (!found) { return 0; } } return count; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` - Each character is visited at most twice. - Linear time. - **Space Complexity:** `O(1)`