Missing Test Case - 1262. Greatest Sum Divisible by Three #33665
Description
LeetCode Username
lcmukesh87
Problem Number, Title, and Link
https://leetcode.com/problems/greatest-sum-divisible-by-three/description/
Bug Category
Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Bug Description
Several brute-force / exponential-time subset-sum solutions incorrectly pass this problem.
The problem constraints allow:
nums.length <= 40000
nums[i] <= 10000
However, the hidden test cases never include worst-case inputs that force exponential recursion. As a result, DFS subset-sum solutions without memoization are accepted, even though they should TLE or overflow recursion depth for valid constraint-sized inputs.
This indicates missing stress test cases.
Language Used for Code
Java
Code used for Submit/Run operation
class Solution {
static boolean isPossible(int arr[],int tar,int idx){
if(tar == 0)return true;
if(tar<0 || idx>=arr.length)return false;
return isPossible(arr,tar-arr[idx],idx+1) || isPossible(arr,tar,idx+1);
}
public int maxSumDivThree(int[] nums) {
int sum = 0;
for(int num:nums){
sum += num;
}
int extra = sum%3;
if(extra == 0)return sum;
while(!isPossible(nums,extra,0)){
extra += 3;
}
return sum-extra;
}
}Expected behavior
Inefficient brute force / DFS subset-sum solutions should time out for valid constraint-sized inputs (e.g., n=40,000).
A valid test suite should detect and reject exponential solutions.
Screenshots
Additional context
This issue affects problem 1262 - Greatest Sum Divisible by Three.
The current test suite does not include any worst-case input where:
- nums.length is near 40,000
- nums[i] are all values ≡ 1 (mod 3)
- subset-sum targets like 1, 4, 7, ... require deep recursion
As a result, several exponential-time solutions that explore 2^n states
incorrectly pass. Adding a stress test with large uniform values
(e.g., 10000 repeated 40000 times) will correctly reject such solutions.