Created
March 20, 2019 11:25
-
-
Save matdziu/cedd3623e6e63f6491bf85eb810ccf7f to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| typealias Frequency = Int | |
| // O(n^2) | |
| fun performTask(a: List<Int>, b: List<Int>, p: Int): List<Int> { | |
| if (isPrime(p)) { | |
| val frequencyMap: HashMap<Int, Frequency> = hashMapOf() | |
| for (currentElem in b) { | |
| if (frequencyMap[currentElem] == null) { | |
| var currentElemFrequency: Frequency = 0 | |
| for (elem in b) { | |
| if (currentElem == elem) currentElemFrequency += 1 | |
| } | |
| frequencyMap[currentElem] = currentElemFrequency | |
| } | |
| } | |
| val filteredFrequencyMap: HashMap<Int, Frequency> = hashMapOf() | |
| for (entry in frequencyMap) { | |
| if (entry.value == p) filteredFrequencyMap[entry.key] = entry.value | |
| } | |
| val elementsToFilter = filteredFrequencyMap.keys | |
| val output = arrayListOf<Int>() | |
| for (elem in a) { | |
| var addElem = true | |
| for (elemToFilter in elementsToFilter) { | |
| if (elem == elemToFilter) { | |
| addElem = false | |
| break | |
| } | |
| } | |
| if (addElem) output.add(elem) | |
| } | |
| return output | |
| } else throw IllegalArgumentException("Argument value should be a prime number") | |
| } | |
| // https://en.wikipedia.org/wiki/Primality_test | |
| // O(n^(1/2)) | |
| fun isPrime(p: Int): Boolean { | |
| if (p <= 1) return false | |
| if (p <= 3) return true | |
| if (p % 2 == 0 || p % 3 == 0) return false | |
| var i = 5 | |
| while (i * i <= p) { | |
| if (p % i == 0 || p % (i + 2) == 0) return false | |
| i += 6 | |
| } | |
| return true | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment