Discussion on: Daily Challenge #78 - Number of Proper Fractions with Denominator d

View post

A Swift solution:

import Foundation

/*
    gcdRecurse:  finds GCD of two numbers using the recursive algorithm

    @param num: positive Int to find GCD of
    @param num2: second positive Int to find GCD of

    @return Int which is the GCD of num & num2
 */
func gcdRecurse(_ num:Int, _ num2:Int) -> Int {
    let remainder = (num2 % num)

    if remainder != 0 {
        return gcdRecurse(remainder, num)
    } else {
        return num
    }
}

/*
   properFractions:  Challenge function, finds total number of proper fractions possible for a given number.

   @param n: positive Int to find number of fractions for.

   @return Int which is the total number of proper fractions.
*/
func properFractions(_ num:Int) -> Int {
    var count = 0

    for n in 1..<num {
        if (gcdRecurse(num, n) == 1) {
            count += 1
        }
    }

    return count
}

print("Example 1:   1   ->  ", properFractions(1))     //  0
print("Example 2:   2   ->  ", properFractions(2))     //  1
print("Example 3:   5   ->  ", properFractions(5))     //  4
print("Example 4:   15  ->  ", properFractions(15))    //  8
print("Example 4:   25  ->  ", properFractions(25))    //  20

print("\n\nPassed all tests:    ", (properFractions(1) == 0 &&
                                    properFractions(2) == 1 &&
                                    properFractions(5) == 4 &&
                                    properFractions(15) == 8 &&
                                    properFractions(25) == 20), "\n\n")

Output:

Example 1:   1   ->   0
Example 2:   2   ->   1
Example 3:   5   ->   4
Example 4:   15  ->   8
Example 4:   25  ->   20


Passed all tests:     true 


Program ended with exit code: 0

Had to implement a GCD function, as I didn't find one in the standard Swift library(if anyone knows different, let me know!)

Otherwise pretty straight forward, choose to go with brute force for-loop and a counter, as I found after some testing the array functions like .filter() / .map() / .reduce() are SCARY slow...