Solutions for Divisible by X

    • @Glenndiuby
    • @Michael, submitted in Python 3, achived 100% score
    from collections import defaultdict
    import json
    # Returns true if arr[0..n-1] can be
    # divided into pairs with sum
    # divisible by k.
    
    
    def canPairs(arr, n, k):
    
        # An odd length array cannot
        # be divided into pairs
        if (n & 1):
            return 0
    
        # Create a frequency array to
        # count occurrences of all
        # remainders when divided by k.
        freq = defaultdict(lambda: 0)
    
        # Count occurrences of all remainders
        for i in range(0, n):
            freq[((arr[i] % k) + k) % k] += 1
    
        # Traverse input array and use
        # freq[] to decide if given array
        # can be divided in pairs
        for i in range(0, n):
    
            # Remainder of current element
            rem = ((arr[i] % k) + k) % k
    
            # If remainder with current element
            # divides k into two halves.
            if (2 * rem == k):
    
                # Then there must be even occurrences
                # of such remainder
                if (freq[rem] % 2 != 0):
                    return 0
    
            # If remainder is 0, then there
            # must be two elements with 0 remainde
            elif (rem == 0):
                if (freq[rem] & 1):
                    return 0
    
                # Else number of occurrences of
                # remainder must be equal to
                # number of occurrences of
                # k - remainder
            elif (freq[rem] != freq[k - rem]):
                 return 0
    
        return 1
    
    def solve(arr,k):
    # Function call
        if (canPairs(arr, len(arr), k)):
            return "True"
        else:
            return "False"