Memory Optimization | Together C & C++ | Page 1

cedar raptor Sep 15, 2023, 3:01 AM

#

Hello everyone,

I'm excited to have joined this server. I've recently started working through some leetcode to refresh my skills before I return to college after a couple year hiatus. I have been working through problem 69, sqrtx. (TLDR- write a function that returns the square root of an integer, rounded down to the nearest integer.) I've managed to come up with a solution that has a pretty fast runtime, but the memory is ~10th percentile.

I don't really have any idea how to manage memory and I would classify myself as a beginner, and at the moment I'm more concerned about solving problems than optimizing, but I was just curious how someone more experienced would think through the process of reducing memory usage. If there are any resources I can look into on this topic, they would be appreciated as well.

My code is below.

Thanks in advance!

class Solution {
public:
    int mySqrt(int x) {
        

        if (x >= 2147395600) // need this check to avoid integer overflow errors 
            {
                return 46340;
            }

        int upperBound = 46341;
        int lowerBound = 0;
        int guess = round ((upperBound-lowerBound) / 2); // start in the middle
        while (!(guess * guess <= x && x < (guess+1) * (guess+1))) // while we don't have a valid guess
        {
            /*
            std::cout <<"x:    " << x <<"\n";
            std::cout <<"Guess:    " << guess << "\n";
            std::cout << "Guess ^2: " << guess*guess << "\n";
            std::cout<< "Upper bound:  " << upperBound <<"\n";
            std::cout<< "Lower bound:  " << lowerBound <<"\n";
            */
            if (guess * guess > x) // if the guess is too big, guess at half the distance from lower bound to the guess 
            {
                upperBound = guess;
                guess =  round((upperBound-lowerBound) / 2) + lowerBound;
            } else // if the guess is too small, add half the distance 
            {
                lowerBound = guess;
                guess = round ((upperBound-lowerBound) / 2) + lowerBound;
            }

        }
    return guess;
    }
    



};

zenith waspBOT Sep 15, 2023, 3:01 AM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

pearl seal Sep 15, 2023, 5:41 AM

#

thats strange, u didnt allocate any memory tho.

#

maybe try removing the std::cout see if that helps

deft gull Sep 15, 2023, 8:44 AM

#

you would be right not to concern yourself with leetcode metrics on memory, stuff like that isn't that important unless it becomes a problem (not at least when you're just getting started).
my guess on how people achieved a lower memory print than your solution is that they just used std::sqrt from <cmath>, which typically uses compiler instrinsics, instead of spinning up an iterative algorithm like you did, which needs several integers for its own book-keeping.

#

cout may also play a part in this, as mentioned above

#Memory Optimization