Given an array arr[] containing integers of size N and a number k, the task is to find the XOR of array elements that are divisible by a given number k in Python.
Examples:
Input: arr[] = {3, 9, 16, 12, 13, 15} , k = 3
Output: 25
Explanation: Only 3,9,12,15 are divisible by 3, XOR = 3^9^12^15 = 9
Input: arr[] = { 3, 9, 12, 13, 15, 2 , 6, 18 } , k=2
Output:
Explanation: Only 12,2,6,18 are divisible by 2, XOR= 12^2^6^18 = 26
Approach:
In order to find the XOR of numbers that are divisible by a given number in the array, we simply iterate through the array and find if an element is divisible by k or not, and then we XOR using the ‘^’ operator. Therefore, the following steps are followed to compute the answer:
- Create a variable to store the XOR of the array elements as a result.
- For each element in the array, check if an element is divisible by a given number or not.
- Find the XOR of the number and store it in the result variable using the ‘^’ operator.
- Finally, the result variable stores the XOR of all array elements which are divisible by the given number k.
Below is the implementation of the above approach:
Python3
def xorOfArray(arr, k): # variable to store result result = 0 # check if each element # is divisible by given number. for i in arr: if i % k == 0: result = result ^ i return result# Driver Codeif __name__ == '__main__': arr = [3, 9, 12, 13, 15, 2, 6, 18] # Function call k = 2 print(xorOfArray(arr, k)) |
26
Complexity Analysis:
Time Complexity: O(n)
Space Complexity: O(1)
Method 2: Using the filter() function :
Step-by-Step Approach :
- First, let’s define an array named my_array.
- Then define a divisor.
- Now, use the filter() function to create an iterator divisible_nums containing only the elements in my_array that are divisible by divisor.
- Initialize a variable Gfgresult to 0.
- Use a for loop to iterate over divisible_nums.
- For each element in divisible_nums, compute its XOR with the Gfgresult using the bitwise XOR operator ^ and store the result back in Gfgresult.
- Print the value of Gfgresult.
Python3
# Define an arraymy_array = [3, 9, 12, 13, 15, 2, 6, 18]# Define the given numberdivisor = 2# Use the filter() function to create an iterator of elements that are divisible by the given numberdivisible_nums = filter(lambda x: x % divisor == 0, my_array)# Initialize a variable to store the XOR resultGfgresult = 0# Use a for loop to calculate the XOR of elements that are# divisible by the given number and store the result in the result variablefor num in divisible_nums: Gfgresult ^= num# Print the XOR resultprint(Gfgresult) |
26
Complexity Analysis:
Time Complexity: O(n)
This is because the filter function takes O(n) time to create the iterator containing the elements that are divisible by the given number, where n is the length of the input array. Now the for loop iterates over the numbers that are divisible by divisor for a constant number of iteration, so we can say that the overall time complexity will be O(n).
Space Complexity: O(1)
This is because we are only using few variables to store the input array, the divisor, divisible_sum, and the Gfgresult and the space used by these variables does not depend on the size of the input array. So we can say that the overall space complexity will be O(1).
Method #3: using bit manipulation
- Initialize a variable xor to zero.
- For each bit position from the least significant bit to the most significant bit:
- Initialize a variable count to zero.
- For each element num in the array:
- If the num is divisible by the given number and the bit at the current bit position is set in num, increment count.
- If the count is odd, set the bit at the current bit position in xor.
- Return the final value of xor.
Python3
def xorOfArray(arr, k): xor = 0 for i in range(31, -1, -1): # iterate through bit positions from MSB to LSB count = 0 for num in arr: if num % k == 0 and num & (1 << i): # check if num is divisible by k and bit i is set count += 1 if count % 2: # if count is odd, set bit i in xor xor |= 1 << i return xor# Driver Codeif __name__ == '__main__': arr = [3, 9, 12, 13, 15, 2, 6, 18] # Function call k = 2 print(xorOfArray(arr, k)) |
26
The time complexity is O(n * log(max_num)), where n is the length of the input array and max_num is the maximum value in the input array.
The space complexity is O(1) because we only use a fixed number of variables.
