Divisible Game | Leetcode 3984

class Solution {
    #define MOD 1000000007

    void getPrimes(vector<int>& nums,set<int>& primes){
        for(int ele: nums){
            for(int i=2;i*i<=ele;++i){
                if(ele%i==0){
                    primes.insert(i);
                    while(ele%i==0)
                        ele/=i;
                }
            }
            if(ele>1)
                primes.insert(ele);
        }
    }

    int kadanesAlgoScore(vector<int>& nums,const int& prime){
        int curr_sum = 0;
        int max_sum = INT_MIN;
        for(int i=0;i<nums.size();++i){
            if(nums[i]%prime==0)    curr_sum += nums[i];
            else                    curr_sum -= nums[i];

            max_sum = max(max_sum,curr_sum);
            if(curr_sum < 0)
                curr_sum = 0;
        }
        return max_sum;
    }
public:
    int divisibleGame(vector<int>& nums) {
        //Step-1: Get all primes which can divide any nums[i]
        set<int> primes;
        getPrimes(nums,primes);
        if(primes.size()==0)
            primes.insert(2);

        //Step-2: Get smallest prime with highest score
        int max_score = INT_MIN;
        int k;
        for(int prime: primes){
            int curr_score = kadanesAlgoScore(nums,prime);
            if(max_score < curr_score){
                max_score = curr_score;
                k = prime;
            }
        }
        max_score = ((1LL * max_score % MOD) * k) % MOD;
        return (max_score + MOD) % MOD;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    private static final int MOD = 1000000007;

    private void getPrimes(int[] nums, Set<Integer> primes) {
        for (int ele : nums) {
            for (int i = 2; i * i <= ele; ++i) {
                if (ele % i == 0) {
                    primes.add(i);
                    while (ele % i == 0) {
                        ele /= i;
                    }
                }
            }
            if (ele > 1) {
                primes.add(ele);
            }
        }
    }

    private int kadanesAlgoScore(int[] nums, int prime) {
        int currSum = 0;
        int maxSum = Integer.MIN_VALUE;
        
        for (int num : nums) {
            if (num % prime == 0) {
                currSum += num;
            } else {
                currSum -= num;
            }

            maxSum = Math.max(maxSum, currSum);
            if (currSum < 0) {
                currSum = 0;
            }
        }
        return maxSum;
    }

    public int divisibleGame(int[] nums) {
        // Step-1: Get all primes which can divide any nums[i]
        // TreeSet maintains the ascending order required for correct tie-breaking
        Set<Integer> primes = new TreeSet<>();
        getPrimes(nums, primes);
        
        if (primes.isEmpty()) {
            primes.add(2);
        }

        // Step-2: Get smallest prime with highest score
        int maxScore = Integer.MIN_VALUE;
        int k = -1;
        
        for (int prime : primes) {
            int currScore = kadanesAlgoScore(nums, prime);
            if (maxScore < currScore) {
                maxScore = currScore;
                k = prime;
            }
        }
        
        // Handle negative modulo correctly in Java
        long ans = ((long) maxScore % MOD * k) % MOD;
        return (int) ((ans + MOD) % MOD);
    }
}

#Python
from typing import List

class Solution:
    def divisibleGame(self, nums: List[int]) -> int:
        MOD = 1000000007
        primes = set()
        
        # Step-1: Get all primes which can divide any nums[i]
        for ele in nums:
            i = 2
            while i * i <= ele:
                if ele % i == 0:
                    primes.add(i)
                    while ele % i == 0:
                        ele //= i
                i += 1
            if ele > 1:
                primes.add(ele)
                
        if not primes:
            primes.add(2)
            
        # Step-2: Get smallest prime with highest score
        max_score = float('-inf')
        k = -1
        
        # sorted() is required because standard Python sets are unordered
        for prime in sorted(primes):
            curr_sum = 0
            curr_max = float('-inf')
            
            for num in nums:
                if num % prime == 0:
                    curr_sum += num
                else:
                    curr_sum -= num
                    
                if curr_sum > curr_max:
                    curr_max = curr_sum
                    
                if curr_sum < 0:
                    curr_sum = 0
                    
            if max_score < curr_max:
                max_score = curr_max
                k = prime
                
        # Python natively handles negative modulo
        ans = (max_score * k) % MOD
        return ans
*/