C++ Square Root Extraction Method (6ms) v.s. Brute-force attack (23 ms)


  • 0

    (1) Square Root Extraction Method: 6ms

    class Solution {
    public:
        int mySqrt(int x) {
    		int ans = 0;
    		if(x < 2)
    			ans = x;
    		else
    		{
    			int bit = ceil(log10(x)); // original digit bit
    			int n = ceil(ceil(log10(x)) / 2); // sqrt digit bit
    			int A = x;
    
    			vector<int> num(n, 0);
    			int i = n - 1;
    			while(i >= 0)
    			{
    				int r = A % 100;
    				A = (A - r) / 100;
    				num[i] = r;
    				--i;
    			}
    
    			int r = 0;
    			int a = 0;
    			int product = 0;
    			int sum = 0;
    			vector<int> sq(n, 0);
    			for(int i = 0; i < n; ++i)
    			{
    				r += num[i];
    				int b = 0;
    				for(int j = 0; j <= 10; ++j)
    				{
    					if((sum * 10 + j) * j > r)
    					{
    						b = j - 1;
    						break;
    					}
    				}
    				product = (sum * 10 + b) * b;
    				sum = (sum * 10 + b) + b;
    
    				r -= product;
    				r *= 100;
    				sq[i] = b;
    			}
    
    			for(int i = 0; i < n; ++i)
    			{
    				ans += sq[i] * pow(10, n - i - 1);
    			}
    		}
            return ans;
        }
    };
    

    (2) Brute-force attack: 23 ms

    class Solution {
    public:
        int mySqrt(int x) {
    		int ans = 0;
    		if(x < 2)
    			ans = x;
    		else
    		{
    			// Brute-force attack: 23 ms
    			long long r = 0;
    			long long n = 0;
    			while(r <= x)
    			{
    				++n;
    				r = n * n;
    			}
    			ans = n - 1;
    		}
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.