Thread: Finding common values in the rows of a vector [Need Help]

  1. #1
    Registered User
    Join Date
    Sep 2018
    Posts
    194

    Finding common values in the rows of a vector [Need Help]

    Can somebody give me a hand with this? I'm doing this for a an application that would print of LCM and GCD (lowest common factor and greatest common divisor) with steps.

    I need to get the common factors so I can highlight them when I'm printing them under factors. I tried googling but I could only find programs that would directly find LCM or GCD. It's important I have all the factors.

    The best I could come up with:
    Code:
    int main() {
        vector <float> operands = { 9, 9, 4 };
        vector < vector <float> > factors;
        vector < vector <float> > factors_temp;
        vector <float> common_factors;
    
        for (const auto& x : operands)
            factors.push_back(prime_factors(x)); // returns a vector 
        
        factors_temp = factors;
    
        for (unsigned int i = 0; i < factors_temp.size(); i++) {
            for (unsigned int j = 0; j < factors_temp[i].size(); j++) {
    
                for (unsigned int k = 0; k < factors_temp.size(); k++) {
                    for (unsigned int l = 0; l < factors_temp[k].size(); l++) {
                        if (k == i)
                            continue;
    
                        if (factors_temp[i][j] == factors_temp[k][l]) {
                            common_factors.push_back(factors_temp[i][j]);
                            factors_temp[i].erase(factors_temp[i].begin() + j);
                            factors_temp[k].erase(factors_temp[k].begin() + l);
                        }
                    }
                }
            }
        }
    
        for (const auto& x : common_factors)
            cout << x << "\t";
    
        cin.get();
        return 0;
    }
    The logic is completely faulty though. It occasionally works for two operands.

    Oh and also I need to erase common factors from the rows and columns themselves. (So they won't repeat while printing out, unless there is a better logic to this)

    Thanks for reading, cheers!


    here's the other part of the code:
    Code:
    #include <iostream>
    #include <vector>
    #include <string>
    #include <Windows.h>
    
    using namespace std;
    
    void SetColor(int ForgC) // source: https://stackoverflow.com/questions/29574849/how-to-change-text-color-and-console-color-in-codeblocks
    {
        WORD wColor;
    
        HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
        CONSOLE_SCREEN_BUFFER_INFO csbi;
    
        //We use csbi for the wAttributes word.
        if (GetConsoleScreenBufferInfo(hStdOut, &csbi))
        {
            //Mask out all but the background attribute, and add in the forgournd     color
            wColor = (csbi.wAttributes & 0xF0) + (ForgC & 0x0F);
            SetConsoleTextAttribute(hStdOut, wColor);
        }
        return;
    }
    
    vector <int> prime_factors(int number) {  // over-loaded function
        vector <int> prime_factors = { 1 };
    
        for (int i = 2; i <= number; i++) {
            while (number % i == 0) {
                number /= i;
                prime_factors.push_back(i);
            }
        }
        return prime_factors;
    }
    Last edited by Nwb; 10-05-2018 at 12:23 AM.

  2. #2
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    The reason I'm using a nested vector is to support any number of operands (I don't know a different way)

    What should happen:
    1) Any number of operands 1 to n must be allowed to be given as input
    2) Given elements' factors are found and put as a unique row in 2D vector 'factors' (works) [idk if 2D vector is the way to go]
    3) Elements common in all the rows are deleted in 'factors_temp' (faulty in my script)
    4) Deleted elements that were common are added to new vector called 'common_factors' (faulty in my script)

    (I think my script works for 2 operands)
    If there is more than 2 it says vector out of range
    Last edited by Nwb; 10-05-2018 at 12:44 AM.

  3. #3
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    Alternative logic that I worked on but also failed:
    Code:
        for (size_t i = 0; i < factors.size(); i++) {
            for (size_t j = 0; j < factors[i].size(); j++) {
    
    
                int currently_found = 0;
    
                for (size_t k = 0; k < factors.size(); k++) {
                    if (i == k)
                        continue; 
                    for (size_t l = 0; l < factors[k].size(); l++) {
                        //cout << factors[i][j] << " | " << factors[k][l] << "\n";
                        if (factors[i][j] == factors[k][l])
                            currently_found++;
    
                        if (currently_found == (int)factors.size() - 1)
                            common_factors.push_back(factors[k][l]);
                    }
                    //cout << "\n\n";
                }
            }
    
            cout << "\n";
        }

  4. #4
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    Okay the first logic is just flawed.. The second logic is the way to go but I don't have it figured out yet.. It seems that currently_formed is being incremented for every iteration of the 'l' loop.. that's not right..

    Never thought I would be spending so much time on this thing but GOD HELP ME. :')

  5. #5
    Registered User
    Join Date
    Jun 2017
    Posts
    156
    It's not really clear what you want to do.
    Can you show us the expected output with some input?

  6. #6
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    Quote Originally Posted by OldGuy2 View Post
    It's not really clear what you want to do.
    Can you show us the expected output with some input?
    input:
    Code:
    vector < vector <float> > factors 
    { {1, 2, 3},       //factors of 6
      {1, 2, 2, 3},    //factors of 12
      {1, 3, 3} };     //factors of 9
    output:
    Code:
    vector <float> common_factors = {3} // factor that is in all the three rows
    Basically I'm trying to find common factors, and each row represents the factors of a different number. So we need to find numbers which are in all the three rows and push it into the variable 'common_factor'.



    Makes sense? :P

  7. #7
    Registered User
    Join Date
    Dec 2017
    Posts
    721
    You actually just want the factors of the gcd of the input values. So how about:
    Code:
    #include <iostream>
    #include <vector>
     
    int gcd(int a, int b) {
        return a == 0 ? b : gcd(b % a, a);
    }
     
    int gcda(const int *a, int n) {
        int d = a[0];
        for (int i = 1; i < n; i++)
            d = gcd(a[i], d);
        return d;
    }
     
    auto factors(int n) {
        std::vector<int> f;
        if (n > 1) {
            while (n % 2 == 0) {
                f.push_back(2);
                n /= 2;
            }
            for (int i = 3; n != 1; i += 2)
                while (n % i == 0) {
                    f.push_back(i);
                    n /= i;
                }
        }
        return f;
    }
     
    int main() {
        int a[4] = { 3*7, 2*3*5*7, 2*2*3*7, 3*3*7*7 };
        auto f = factors(gcda(a, 4));
        for (auto x: f)
            std::cout << x << ' ';
        std::cout << '\n';
    }
    BTW, 1 isn't really a prime factor. And you want to use integers, not floating point, although you might want to use long or long long.
    Last edited by john.c; 10-05-2018 at 08:57 AM.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  8. #8
    Registered User
    Join Date
    Jun 2017
    Posts
    156
    Consider using std::set_intersection.
    I guess you want the factors to be sorted and unique so best to store them in a std::set.

  9. #9
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    Quote Originally Posted by john.c View Post
    You actually just want the factors of the gcd of the input values. So how about:
    Code:
    #include <iostream>
    #include <vector>
     
    int gcd(int a, int b) {
        return a == 0 ? b : gcd(b % a, a);
    }
     
    int gcda(const int *a, int n) {
        int d = a[0];
        for (int i = 1; i < n; i++)
            d = gcd(a[i], d);
        return d;
    }
     
    auto factors(int n) {
        std::vector<int> f;
        if (n > 1) {
            while (n % 2 == 0) {
                f.push_back(2);
                n /= 2;
            }
            for (int i = 3; n != 1; i += 2)
                while (n % i == 0) {
                    f.push_back(i);
                    n /= i;
                }
        }
        return f;
    }
     
    int main() {
        int a[4] = { 3*7, 2*3*5*7, 2*2*3*7, 3*3*7*7 };
        auto f = factors(gcda(a, 4));
        for (auto x: f)
            std::cout << x << ' ';
        std::cout << '\n';
    }
    BTW, 1 isn't really a prime factor. And you want to use integers, not floating point, although you might want to use long or long long.
    Dude I really appreciate it that you took the time to write that!
    But umgh I need the common factors too.. hehe. So how would I do that?

    Oh and float is because I plan to support finding GCD and LCM for floating values as well. And yea I might need to use long float, thanks!

    (OH WAIT, I just realized.. prime factors of the GCD would be the common factors of the terms right..!)

    phew thanks a lot.
    Last edited by Nwb; 10-05-2018 at 10:00 AM.

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    721
    There is no long float. Instead it's called double. But there's also long double.
    For ints there's long and long long.

    And I've never heard of a GCD of non-integers. Can you give an example?
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  11. #11
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    Quote Originally Posted by john.c View Post
    There is no long float. Instead it's called double. But there's also long double.
    For ints there's long and long long.

    And I've never heard of a GCD of non-integers. Can you give an example?
    source: H.C.F. and L.C.M. of Decimals | H.C.F. and L.C.M. | Worked-out Examples

    1. Find the H.C.F. and the L.C.M. of 1.20 and 22.5
    Solution:
    Given, 1.20 and 22.5
    Converting each of the following decimals into like decimals we get;
    1.20 and 22.50
    Now, expressing each of the numbers without the decimals as the product of primes we get

    120 = 2 2 2 3 5 = 23 3 5

    2250 = 2 3 3 5 5 5 = 2 32 53

    Now, H.C.F. of 120 and 2250 = 2 3 5 = 30
    Therefore, the H.C.F. of 1.20 and 22.5 = 0.30 (taking 2 decimal places)

    L.C.M. of 120 and 2250 = 23 32 53 = 9000
    Therefore, L.C.M. of 1.20 and 22.5 = 90.00 (taking 2 decimal places)


    2. Find the H.C.F. and the L.C.M. of 0.48, 0.72 and 0.108
    Solution:
    Given, 0.48, 0.72 and 0.108
    Converting each of the following decimals into like decimals we get;
    0.480, 0.720 and 0.108

    Now, expressing each of the numbers without the decimals as the product of primes we get
    480 = 2 2 2 2 2 3 5 = 25 3 5

    720 = 2 2 2 2 3 3 5 = 24 32 5

    108 = 2 2 3 3 3 = 22 33

    Now, H.C.F. of 480, 720 and 108 = 22 3 = 12
    Therefore, the H.C.F. of 0.48, 0.72 and 0.108 = 0.012 (taking 3 decimal places)

    L.C.M. of 480, 720 and 108 = 25 33 5 = 4320
    Therefore, L.C.M. of 0.48, 0.72, 0.108 = 4.32 (taking 3 decimal places)


    3. Find the H.C.F. and the L.C.M. of 0.6, 1.5, 0.18 and 3.6
    Solution:
    Given, 0.6, 1.5, 0.18 and 3.6
    Converting each of the following decimals into like decimals we get;

    0.60, 1.50, 0.18 and 3.60
    Now, expressing each of the numbers without the decimals as the product of primes we get
    60 = 2 2 3 5 = 22 3 5

    150 = 2 3 5 5 = 2 3 52

    18 = 2 3 3 = 2 32

    360 = 2 2 2 3 3 5 = 23 32 5

    Now, H.C.F. of 60, 150, 18 and 360 = 2 3 = 6
    Therefore, the H.C.F. of 0.6, 1.5, 0.18 and 3.6 = 0.06 (taking 2 decimal places)

    L.C.M. of 60, 150, 18 and 360 = 23 32 52 = 1800
    Therefore, L.C.M. of 0.6, 1.5, 0.18 and 3.6 = 18.00 (taking 2 decimal places)

    source: H.C.F. and L.C.M. of Decimals | H.C.F. and L.C.M. | Worked-out Examples

  12. #12
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,612
    I've also never heard of this. However, the math is based on using a scale factor. If you can figure out a suitable base-ten scale factor for your input, then you can do the math in integers with all of the significant digits, (as you've shown) and present the output in decimal format.

  13. #13
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    By the way I ended up using this function (for future readers ):
    Code:
    int gcd(int a, int b) {
        return a == 0 ? b : gcd(b % a, a);
    }
    
    int find_gcd(vector <int> arr) {
        int result = arr[0];
        for (int i = 1; i < arr.size(); i++)
            result = gcd(arr[i], result);
        return result;
    }
    
    // example input:
        cout<< find_gcd({ 2, 4, 5 });
    It originally took an array as input, but vectors are better right?

  14. #14
    Registered User
    Join Date
    May 2010
    Posts
    4,456
    Do you realize that you're copying that vector every time you call find_gcd()?

    You may want to consider passing by reference/const reference instead.

  15. #15
    Registered User
    Join Date
    Sep 2018
    Posts
    194
    Quote Originally Posted by jimblumberg View Post
    Do you realize that you're copying that vector every time you call find_gcd()?

    You may want to consider passing by reference/const reference instead.
    I'm sorry I'm a newbie at this so I don't know what you meant by copying that vector every time.. can you please elaborate? Also what is passing by reference and how do I do it?
    Thanks jim

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 2D Array Problem - Finding each rows minimum value
    By Jordan Velez in forum C++ Programming
    Replies: 1
    Last Post: 05-11-2015, 01:04 PM
  2. Finding a common suffix
    By echo1525 in forum C Programming
    Replies: 3
    Last Post: 11-12-2012, 12:35 AM
  3. finding common numbers
    By BB89 in forum C Programming
    Replies: 14
    Last Post: 11-10-2009, 08:22 AM
  4. finding most common char in a string
    By scwizzo in forum C++ Programming
    Replies: 6
    Last Post: 11-23-2007, 01:22 PM
  5. Finding the most common char
    By Mikro in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 09:00 AM

Tags for this Thread