Last active
September 29, 2020 21:53
-
-
Save andr-ec/b3bc4acc3e48805c5a3f84d0a0ebfdc0 to your computer and use it in GitHub Desktop.
Solution.swift
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
import Foundation | |
// Complete the longestSequence function below. | |
/// Finds the largest prime divisor | |
func findLargestDivisor(for number: Int)-> Int { | |
let maxInt = Int(sqrt(Double(number)).rounded(.up) + 1) | |
for possibleDivisor in 2..<maxInt{ | |
if number % possibleDivisor == 0 { | |
return number / possibleDivisor | |
} | |
} | |
return 1 | |
} | |
func getMaxMoves(for number: Int) -> Int { | |
var movesCount = 0 | |
var replacementNumber = number | |
// finding the largest divisor and replacing each iteration. | |
// largest divisor gives you the amount of moves at each iteration in reverse. | |
while replacementNumber > 1 { | |
// 2, 2, 2, 3 | |
let largestDivisor = findLargestDivisor(for: replacementNumber) // 12, 6, 3, 1 | |
replacementNumber = largestDivisor | |
movesCount += largestDivisor | |
} | |
movesCount += number | |
// can be verified by storing the smallest divisors (largest/replacementnumber) at each iteration and splitting into the amount of each smallest divisor start with the last one and working backwards | |
return movesCount | |
} | |
func longestSequence(a: [Int]) -> Int { | |
// Return the length of the longest possible sequence of moves. | |
return a.map(getMaxMoves(for:)).reduce(0, +) | |
} | |
let stdout = ProcessInfo.processInfo.environment["OUTPUT_PATH"]! | |
FileManager.default.createFile(atPath: stdout, contents: nil, attributes: nil) | |
let fileHandle = FileHandle(forWritingAtPath: stdout)! | |
guard let n = Int((readLine()?.trimmingCharacters(in: .whitespacesAndNewlines))!) | |
else { fatalError("Bad input") } | |
guard let aTemp = readLine() else { fatalError("Bad input") } | |
let a: [Int] = aTemp.split(separator: " ").map { | |
if let aItem = Int($0.trimmingCharacters(in: .whitespacesAndNewlines)) { | |
return aItem | |
} else { fatalError("Bad input") } | |
} | |
guard a.count == n else { fatalError("Bad input") } | |
let result = longestSequence(a: a) | |
fileHandle.write(String(result).data(using: .utf8)!) | |
fileHandle.write("\n".data(using: .utf8)!) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment