DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #130 - GCD Sum

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).

For example:
Given sum = 12 and gcd = 4...

solve(12,4) = [4,8].
The two numbers 4 and 8 sum to 12 and have a gcd of 4.

solve(12,5) = -1.
No two numbers exist that sum to 12 and have gcd of 5.

solve(10,2) = [2,8].
Note that [4,6] is also a possibility but we pick the one with the lower first element: 2 < 4, so we take [2,8].

Good luck.


This challenge comes from KenKamau on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (8)

Collapse
 
avalander profile image
Avalander • Edited

Haskell.

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 ]
Collapse
 
craigmc08 profile image
Craig McIlwrath

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.

Collapse
 
avalander profile image
Avalander • Edited

You might be right, I had forgotten about that tiny detail.

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.

Collapse
 
rulikkk profile image
Rustem Mustafin

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
Answer: GCD, Sum - GCD
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

Collapse
 
midhetfatema94 profile image
Midhet Sulemani

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)
}
Collapse
 
juanrodriguezarc profile image
Juan Rodríguez • Edited
const solve = (s,g) => (s%g) ? -1 : [g,(s / g-1)*g]
Collapse
 
_bkeren profile image
'' • Edited

JavaScript ES6

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

Collapse
 
meave9786 profile image
meave9786

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.