Question: Find the element in the array list that occurs odd number of times
Description of input: All input lists will contain only one number that occurs odd number of times
Example:
input = [9,3,9,3,9,7,9]
output = 7
Logic:
1. Sort the data set in ascending order
2. Check all the even indiced numbers in the list if they match the next element
3. In case they match that number(at the even index) is present even number of times, when the numbers dont match the number it means that the number(at the even index) occurs odd number of times
Code flow or Pseudo Code:
1. Check for length of input list if length is 1 output is that number else go to 2
2. For even numbered index check the sorted list if the next element matches the number in this position
3. If it doesnot match we have the number which occurs odd number of times else we have to repeat step 2 with the next even index
4. If there is no match until the last even index then the number that has odd occurances is the number in the last even index
Understanding syntax:
line 5: sorted(A) - will sort the list A in ascending order
line 12: A[i]^A[i+1] - xor function where the elements involved are integers gives 0 when numbers are the same and non zero number when numbers dont match
Let us try with few examples:
Test case 1: [9,3,9,3,9,7,9]
Sorted list - [3,3,7,9,9,9,9]
All even indices - 0,2,4,6
Comparision indices - 0,1 - corresponding elements - 3,3 - elements matching
Comparision indices - 2,3 - corresponding elements - 7,9 - elements don't match - number with odd number of occurances is 7
How do we check for element matching?
Use xor function. For a ^ b output is 0 if a=b and output is a non zero if a!=b; where a,b are integers.
Test case 2: [a] - single integer in the array the output must be the single integer that is present
Test case 3: In case the last element in the sorted array is the number with odd occurance in the array.
input array: [2,3,4,5,3,2,4,5,7]
sorted array: [2,2,3,3,4,4,5,5,7]
output: 7
Since the number of elements is always odd the last even index will not have a pair incase the number with odd occurance is not found before the last even index in the array hence a condition must be present in the 'for loop' to accomodate for this
For the even index 8 there is no element in position 9 to compare it to for checking hence the code must accomodate for this.
This was my code submission which got a 100% score on codility for correctness and time complexity. What was your approach? How much did you score? Did the article help you in any way? Do you have any more questions for me? Leave your comments below and let me know. Don't forget to like, share and subscribe.
Description of input: All input lists will contain only one number that occurs odd number of times
Example:
input = [9,3,9,3,9,7,9]
output = 7
Logic:
1. Sort the data set in ascending order
2. Check all the even indiced numbers in the list if they match the next element
3. In case they match that number(at the even index) is present even number of times, when the numbers dont match the number it means that the number(at the even index) occurs odd number of times
Code flow or Pseudo Code:
1. Check for length of input list if length is 1 output is that number else go to 2
2. For even numbered index check the sorted list if the next element matches the number in this position
3. If it doesnot match we have the number which occurs odd number of times else we have to repeat step 2 with the next even index
4. If there is no match until the last even index then the number that has odd occurances is the number in the last even index
Understanding syntax:
line 5: sorted(A) - will sort the list A in ascending order
line 12: A[i]^A[i+1] - xor function where the elements involved are integers gives 0 when numbers are the same and non zero number when numbers dont match
Let us try with few examples:
Test case 1: [9,3,9,3,9,7,9]
Sorted list - [3,3,7,9,9,9,9]
Comparision indices - 0,1 - corresponding elements - 3,3 - elements matching
Comparision indices - 2,3 - corresponding elements - 7,9 - elements don't match - number with odd number of occurances is 7
How do we check for element matching?
Use xor function. For a ^ b output is 0 if a=b and output is a non zero if a!=b; where a,b are integers.
Test case 2: [a] - single integer in the array the output must be the single integer that is present
Test case 3: In case the last element in the sorted array is the number with odd occurance in the array.
input array: [2,3,4,5,3,2,4,5,7]
sorted array: [2,2,3,3,4,4,5,5,7]
output: 7
Since the number of elements is always odd the last even index will not have a pair incase the number with odd occurance is not found before the last even index in the array hence a condition must be present in the 'for loop' to accomodate for this
For the even index 8 there is no element in position 9 to compare it to for checking hence the code must accomodate for this.
This was my code submission which got a 100% score on codility for correctness and time complexity. What was your approach? How much did you score? Did the article help you in any way? Do you have any more questions for me? Leave your comments below and let me know. Don't forget to like, share and subscribe.
Comments
Post a Comment