Check Array Pairs Divisible by K

📋

Problem

Imagine you have a list of socks, and you want to pair them so that the sum of the sizes of each pair is divisible by a given number K. Can you check if such pairing is possible for all socks?

Given an array of integers nums and an integer k, determine if it is possible to pair all elements of the array such that the sum of each pair is divisible by k. Return true if such a pairing exists, otherwise false.

1 ≤ nums.length ≤ 10^51 ≤ k ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

Edge cases: Array length is odd → falseAll elements are zero and k divides zero → trueElements with remainder 0 must be even in count → false if odd

</>

IDE

def canArrange(nums: list[int], k: int) -> bool:public boolean canArrange(int[] nums, int k)bool canArrange(vector<int>& nums, int k)function canArrange(nums, k)

def canArrange(nums, k):
    # Write your solution here
    pass

class Solution {
    public boolean canArrange(int[] nums, int k) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool canArrange(vector<int>& nums, int k) {
    // Write your solution here
    return false;
}

function canArrange(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueReturning true for arrays with odd length, ignoring that pairing all elements is impossible.✅ Add a check at the start: if len(nums) % 2 != 0: return False

Wrong: falseNot handling remainder 0 elements count parity correctly, returning false even when count is even.✅ Ensure that frequency of remainder 0 elements is even before returning true.

Wrong: falseFailing to verify that frequency of remainder r equals frequency of remainder k-r for all r.✅ Check for all r in 1..k-1 that freq[r] == freq[k-r], else return false.

Wrong: timeoutUsing brute force nested loops O(n^2) approach for large inputs.✅ Implement O(n) solution using remainder frequency map instead of nested loops.

✓

Test Cases

Make sure your solution handles empty and single-element arrays correctly.

Check your logic for remainder 0 elements and complement pairs carefully.

Optimize your solution to use remainder frequency counting instead of nested loops.

t1_01basic

Input{"nums":[1,2,3,4,5,10,6,7,8,9],"k":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Pairs like (1,4), (2,3), (5,10), (6,9), (7,8) all sum to multiples of 5.

💡 Think about pairing elements based on their remainders modulo k.

💡 Use a frequency map of remainders and check if counts complement each other.

💡 Check if count of remainder 0 elements is even and for other remainders freq[r] == freq[k-r].

Why it failed: Returned false or incorrect result due to not pairing elements by remainder complements or mishandling remainder 0 counts. Fix by counting frequencies of nums[i] % k and verifying pairs accordingly.

✓ Correctly pairs elements by remainder complements and handles remainder 0 counts.

t1_02basic

Input{"nums":[1,2,3,4,5,6],"k":7}

Expectedtrue

⏱ Performance - must finish in 2000ms

Pairs (1,6), (2,5), (3,4) sum to multiples of 7.

💡 Focus on remainder frequencies modulo k=7.

💡 Check if for each remainder r, frequency matches frequency of k-r.

💡 Ensure total number of elements is even and remainder 0 count is even.

Why it failed: Incorrect output due to ignoring remainder complement pairs or odd count of remainder 0 elements. Fix by verifying frequency counts for all remainders including zero.

✓ Correctly matches remainder pairs and confirms even counts for remainder 0.

t2_01edge

Input{"nums":[],"k":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty array can be considered trivially paired.

💡 Consider what happens when the array is empty.

💡 An empty array has zero elements, so no pairs needed.

💡 Return true since no elements violate pairing condition.

Why it failed: Returned false or error on empty input. Fix by adding base case: if nums is empty, return true.

✓ Handles empty input correctly by returning true.

t2_02edge

Input{"nums":[1],"k":2}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element cannot form pairs, so return false.

💡 Check if array length is odd.

💡 If odd, pairing all elements is impossible.

💡 Return false immediately if nums length is odd.

Why it failed: Returned true despite odd length. Fix by checking if length of nums is even before pairing.

✓ Correctly returns false for odd length arrays.

t2_03edge

Input{"nums":[0,0,0,0],"k":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

All zeros sum to zero which is divisible by k; count of remainder 0 elements is even.

💡 Check how remainder 0 elements are handled.

💡 Remainder 0 elements must be paired in even counts.

💡 Verify that count of remainder 0 elements is even to return true.

Why it failed: Returned false due to mishandling remainder 0 elements count. Fix by ensuring remainder 0 count is even.

✓ Correctly handles remainder 0 elements with even count.

t3_01corner

Input{"nums":[1,2,3,4,5],"k":3}

Expectedfalse

⏱ Performance - must finish in 2000ms

Array length is odd, so pairing all elements is impossible.

💡 Check if your solution handles odd length arrays correctly.

💡 Verify that you return false immediately if length is odd.

💡 Add a length check at the start to return false if odd.

Why it failed: Returned true despite odd length input. This is the odd length test catching missing length check. Fix by adding length % 2 == 0 condition.

✓ Correctly returns false for odd length arrays.

t3_02corner

Input{"nums":[5,5,5,5,5,5],"k":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

All elements have remainder 0; count is even so pairing is possible.

💡 Check if remainder 0 elements are counted correctly.

💡 Ensure that remainder 0 count is even to allow pairing.

💡 Fix by verifying remainder 0 count parity before returning true.

Why it failed: Returned false due to incorrect handling of remainder 0 elements count. This is the remainder 0 parity test. Fix by checking remainder 0 count is even.

✓ Correctly handles remainder 0 elements with even count.

t3_03corner

Input{"nums":[1,9,2,8,3,7,4,6],"k":10}

Expectedtrue

⏱ Performance - must finish in 2000ms

Pairs like (1,9), (2,8), (3,7), (4,6) sum to multiples of 10.

💡 Check if your solution correctly pairs remainder r with k-r.

💡 Verify frequency counts for all remainders and their complements.

💡 Fix by ensuring freq[r] == freq[k-r] for all r except 0 and k/2 if applicable.

Why it failed: Returned false due to not matching remainder complements correctly. This is the complement remainder pairing test. Fix by verifying freq[r] == freq[k-r].

✓ Correctly pairs elements by remainder complements.

t4_01performance

Input{"nums":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901],"k":100000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, k=100000; solution must run in O(n) or O(n+k) time to complete within 2 seconds.

💡 Brute force O(n^2) will time out for n=100.

💡 Use frequency map of remainders to achieve O(n) time.

💡 Avoid nested loops; count remainders and check complement frequencies.

Why it failed: Solution timed out due to O(n^2) brute force approach. This is the performance test catching complexity issues. Fix by implementing O(n) remainder frequency counting.

✓ Solution runs efficiently in O(n) time using remainder frequency map.

Practice

1. Given the following code, what is the final output of count_nice_subarrays([2,1,2,1], 1)?

easy

A. 4

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace at_most_k(nums, 1)

   Counting subarrays with at most 1 odd: - right=0 (2): odd_count=0, count=1 - right=1 (1): odd_count=1, count=1+(1-0+1)=3 - right=2 (2): odd_count=1, count=3+(2-0+1)=6 - right=3 (1): odd_count=2 >1, shrink left until odd_count=1 left moves from 0 to 1, odd_count=1, count=6+(3-1+1)=9 Total at_most_k(1)=9

2. Step 2: Trace at_most_k(nums, 0)

   Counting subarrays with at most 0 odd: - right=0 (2): odd_count=0, count=1 - right=1 (1): odd_count=1 >0, shrink left to 1, odd_count=0, count=1+(1-1+1)=2 - right=2 (2): odd_count=0, count=2+(2-1+1)=4 - right=3 (1): odd_count=1 >0, shrink left to 3, odd_count=0, count=4+(3-3+1)=5 Total at_most_k(0)=5

3. Final Answer:

   count_nice_subarrays = 9 - 5 = 4

4. Quick Check:

   Rechecking counts confirms 4 subarrays with exactly 1 odd [OK]

Hint: Subtract at_most_k(k-1) from at_most_k(k) [OK]

Common Mistakes:

• Off-by-one in counting subarrays
• Miscounting odd numbers in window
• Forgetting to shrink window correctly

2. You are given an unsorted array of integers and need to find the length of the longest sequence of consecutive integers that appear in the array. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and then scan linearly to find the longest consecutive sequence.

B. For each number, scan the entire array to count consecutive numbers starting from it.

C. Use dynamic programming to store the longest consecutive sequence ending at each number.

D. Use a hash set to track numbers and only start counting sequences from numbers that have no predecessor in the set.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the longest consecutive sequence in an unsorted array efficiently.

2. Step 2: Evaluate approaches for optimality

   Sorting then scanning is O(n log n), brute force scanning is O(n²), and DP is not straightforward here. Using a hash set to track numbers and only starting sequences from numbers without a predecessor ensures each sequence is counted once, achieving O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash set approach avoids redundant work and achieves linear time [OK]

Hint: Only start sequences from numbers without a predecessor [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Trying DP without clear subproblem
• Brute force scanning entire array repeatedly

3. Consider the following code snippet for finding the longest subarray with equal number of 0s and 1s. What is the value of max_length after processing the input [0, 1, 0, 1]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace prefix sums and first_occurrence updates.

   For input [0,1,0,1], prefix sums are: -1, 0, -1, 0 with offset indexing.

2. Step 2: Update max_length when prefix sum repeats.

   At i=1, prefix_sum=0 repeats at index -1 -> length=2; at i=3, prefix_sum=0 repeats again -> length=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Longest balanced subarray is entire array length 4 [OK]

Hint: Prefix sum repeats indicate balanced subarray [OK]

Common Mistakes:

• Off-by-one in length calculation
• Confusing prefix sum indexing
• Ignoring initial prefix sum at -1

4. Consider the following buggy code for finding the longest substring with at most two distinct characters. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line inside while loop missing check to decrement distinct_count when freq hits zero

B. Line where freq[ord(s[right])] is incremented

C. Line inside while loop where freq[ord(s[left])] is decremented

D. Line where distinct_count is incremented when freq is zero

Solution

1. Step 1: Identify the bug

   The code decrements freq for s[left] inside the while loop but does not check if freq reaches zero to decrement distinct_count.

2. Step 2: Consequences of missing check

   Without decrementing distinct_count, the while loop condition distinct_count > 2 never becomes false, causing infinite loop or incorrect window size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing distinct_count decrement inside while loop is a classic subtle bug [OK]

Hint: Check distinct_count update when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement distinct_count
• Incorrect window size calculation
• Not breaking early in brute force

5. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best