4

Suppose you are given a container of ratios and you want to simplify the ratios to the lowest integers.

Input:

std::vector<int> v1 = { 10, 20 , 30, 40 };

Output:

1,2,3,4

How does one solve this for n-sized container? I am looking for general solution, that works for any number of elements and any integer values.

  • 6
    Look for the greatest common divisor and divide all of them. – tkausl Apr 21 at 23:22
  • 1
    ratios are 10/20 and 30/40 or how do the numbers relate to each other? – formerlyknownas_463035818 Apr 21 at 23:47
  • Perhaps you could tell us a little about why you need to do this? I am finding it hard to imagine a use for this operation! – TonyK Apr 22 at 0:26
7

GCD algorithm is associative, which means that GCD(a, b, c, d) is equivalent to GCD(GCD(GCD(a, b), c), d) so we can just run it in a loop and apply to each consecutive pair. Return 1 if sequence is empty as every number is divisible by 1.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int gcd_of_all(const std::vector<int>& values)
{   
    if (values.empty())
        return 1; // division by 1 does nothing

    int result = values[0];
    for (std::size_t i = 1; i < values.size(); ++i)
    {
        result = std::gcd(result, values[i]);
    }

    return result;
}


int main()
{
    std::vector<int> v = { 10, 20, 30, 40 };
    int gcd = gcd_of_all(v);
    std::cout << "gcd: " << gcd << "\n";

    for (int& elem : v)
        elem /= gcd;

    for (int elem : v)
        std::cout << elem << " ";
}

Additional: the reason I used std::size_t i = 1; i < values.size(); ++i instead of the usual int i = 1;... is because if int is used, it triggers compilers warnings because i < values.size() will be comparing numbers of different signess

7

Repeatedly apply std::gcd to all numbers in the vector to find the gcd of all the numbers then divide every element by the gcd.

const int gcd = std::reduce(v1.cbegin(), v1.cend(), 1, [](int a, int b) {
  return std::gcd(a, b);
});
if (gcd != 1) {
  for (int &elem : v1) {
    elem /= gcd;
  }
}
  • 1
    Minor improvement: insert for loop under if (gcd != 1), what can easly happen if any value is prime number. – R2RT Apr 22 at 13:59
  • @R2RT Good point. Added – Kerndog73 Apr 22 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.