Sieve of Eratosthenes to solve a Leetcode problem III

In this case the Sieve is applied directly to the main loop. Notice that you don't need to save off the elements in different arrays, only add them up. Also important to note that composite numbers can be created in multiple ways (for example, 2*6 == 3*4), hence keep track of which ones you have seen before to avoid double counting. No GAI involved, except at the very bottom to compute the Big-O time complexity, which I think it would have been of the order of NLogN, but the true analysis from OpenAI O3 (Advanced Reasoning) is down below. So is the code. Cheers, ACC.

Split Array by Prime Indices - LeetCode

You are given an integer array nums.

Split nums into two arrays A and B using the following rule:

• Elements at  indices in nums must go into array A.
• All other elements must go into array B.

Return the absolute difference between the sums of the two arrays: |sum(A) - sum(B)|.

Note: An empty array has a sum of 0.

 

Example 1:

Input: nums = [2,3,4]

Output: 1

Explanation:

• The only prime index in the array is 2, so nums[2] = 4 is placed in array A.
• The remaining elements, nums[0] = 2 and nums[1] = 3 are placed in array B.
• sum(A) = 4, sum(B) = 2 + 3 = 5.
• The absolute difference is |4 - 5| = 1.

Example 2:

Input: nums = [-1,5,7,0]

Output: 3

Explanation:

• The prime indices in the array are 2 and 3, so nums[2] = 7 and nums[3] = 0 are placed in array A.
• The remaining elements, nums[0] = -1 and nums[1] = 5 are placed in array B.
• sum(A) = 7 + 0 = 7, sum(B) = -1 + 5 = 4.
• The absolute difference is |7 - 4| = 3.

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Code:

    public long SplitArray(int[] nums) {

        if (nums.Length < 2) return nums.Sum();

        HashSet seen = new HashSet();
        long sumComposite = nums[0] + nums[1];
        for (int i = 2; i < nums.Length; i++)
        {
            for (int j = i; j < nums.Length; j++)
            {
                long index = (long)i * j;
                if (index >= nums.Length)
                    break;
                if (!seen.Contains(i * j))
                {
                    seen.Add(i * j);                    
                    sumComposite += nums[i * j];
                }
            }
        }

        long sumAll = 0;
        for (int i = 0; i < nums.Length; i++)
            sumAll += nums[i];

        long sumPrime = sumAll - sumComposite;

        return Math.Abs(sumPrime - sumComposite);
    }

OpenAI O3 (Advanced Reasoning) Big-O Time Complexity Analysis:

### Step‑by‑step cost analysis

Code fragment	Iterations	Cost per iteration	Total cost
if (nums.Length < 2)… & nums.Sum()	≤ n	O(1)	O(n)
sumComposite = nums[0] + nums[1];	1	O(1)	O(1)
Nested loops that fill seen and update sumComposite	see below	O(1)	?
Final for that adds up sumAll	n	O(1)	O(n)
Everything else (hash checks, arithmetic)	—	O(1)	O(1)

The only non‑trivial part is the double loop:

for (int i = 2; i < n; i++)           // outer
    for (int j = i; j < n; j++)       // inner
    {
        long idx = (long)i * j;
        if (idx >= n) break;          // stop inner loop
        …                             // O(1)
    }

---

#### 1. Upper bound on the inner loop length for a fixed i

j runs while i · j < n, starting at j = i.
So the maximum j is ⌊(n – 1)/i⌋, and the number of inner iterations is

$$\bigl\lfloor\tfrac{n-1}{i}\bigr\rfloor - i + 1$$

which is positive only when $i \le \sqrt{n-1}$.
For larger i the inner loop executes zero times (it breaks immediately).

---

#### 2. Total iterations of the double loop

Sum over all relevant i:

$$T(n)=\sum_{i=2}^{\lfloor\sqrt n\rfloor} \left(\Bigl\lfloor\frac{n-1}{i}\Bigr\rfloor - i + 1\right)$$

Ignoring the ±1 constants and replacing the floor with n/i for an upper bound:

$$T(n)\;=\; O\!\left( \sum_{i=2}^{\sqrt n}\frac{n}{i}\;-\; \sum_{i=2}^{\sqrt n} i \right).$$

• Harmonic part: $n\sum_{i=2}^{\sqrt n}\frac1i = n\bigl(H_{\sqrt n}-1\bigr) = n\bigl(\ln\sqrt n + \gamma -1 + o(1)\bigr) = \tfrac{n}{2}\ln n + O(n)$.

• Quadratic tail: $\sum_{i=2}^{\sqrt n} i = \tfrac12(\sqrt n\,)(\sqrt n +1) = O(n)$.

Dominant term: $T(n)=O\!\bigl(n\log n\bigr)$.

---

### 3. Overall time complexity

The nested loop dominates every other O(n) step:

$$\boxed{\;T_{\text{total}}(n)=O\!\bigl(n\log n\bigr)\;}$$

### 4. Space complexity

• HashSet<int> seen can hold at most one entry per array index ⇒ O(n).

• A handful of scalars ⇒ O(1) extra.

---

Result

• Time: O(n log n)

• Space: O(n)