### Daily Challenge #130 - GCD Sum

#### dev.to staff on December 02, 2019

Given the sum and gcd of two numbers, return those two numbers in ascending order. If the numbers do not exist, return -1, (or return NULL in C). ... [Read Full]

A bit ineffective because it generates all possible solutions instead of stopping when it finds the first solution.

``````solve :: Int -> Int -> Maybe (Int, Int)
solve sum target
| solutions == [] = Nothing
| otherwise       = Just (head solutions)
where
solutions = [(a, b) | a <- [1..(sum `div` 2)],
let b = sum - a,
gcd a b == target ]
``````

Correct me if I'm wrong, but it doesn't generate all possible solutions. Haskell is lazy, and because the function only returns the head of the list, only the head can be forced into a value. So the evaluation of the list will stop as soon as a value for the head is found, meaning it does stop when the first solution is found.

Update: I tried with an infinite sequence to generate the solutions and the program didn't get stuck in an infinite loop, so you are right, only the first element of the sequence is generated.

Assume 0 < N <= M
Sum = N + M
GCD = G, so that N = x * G, M = y * G and x, y are relatively prime integers > 0
=>
Sum = x * G + y * G = G * (x + y)
Sum / G should also be integer, otherwise no answer
x + y = Sum / G
We need to take smallest x, so that x, y are relatively prime, so x = 1
=> x = 1 => N = G => M = Sum - G
Test:
1) Solve(12, 4) = 4, 8; GCD(4, 8) = 4; 4 + 8 = 12; OK
2) Solve(12, 5): 12 % 5 > 0 => No Answer; OK
3) Solve(10, 2) = 2, 8; GCD(2, 8) = 2; 2 + 8 = 10; OK

Reiterating to this logic in Swift:

``````import UIKit

func solve(sum: Int, hcf: Int) -> (Int, Int)? {
let x = 1
var y: Int!

y = sum - hcf

let verificationInt: Float = Float((hcf + y)/hcf)
let verificationSum = Int(verificationInt + 1)
if verificationSum % hcf == 0 {
return (hcf*x, y)
}
return nil
}

if let solution = solve(sum: 12, hcf: 5) {
print(solution)
} else {
print(-1)
}
``````

``````const solve = (s,g) => (s%g) ? -1 : [g,(s / g-1)*g]
``````

JavaScript ES6

const solve = (sum,gcd) => {
if(sum%gcd) return -1;
const constantSum = sum / gcd;
return [gcd,(constantSum-1) * gcd]
}

I like to share the blog very much it is the amazing way play the amazing free solitaire really glad for the share me this hope you like it very much.

code of conduct - report abuse