Raíz cuadrada de un número entero

Posted on by Rudeus Greyrat

Dado un entero x, encuentre su raíz cuadrada. Si x no es un cuadrado perfecto, devuelve piso(√x).

Ejemplos: 

Input: x = 4
Output: 2
Explanation:  The square root of 4 is 2.

Input: x = 11
Output: 3
Explanation:  The square root of 11 lies in between
3 and 4 so floor of the square root is 3.

Puede haber muchas maneras de resolver este problema. Por ejemplo, el método babilónico es una forma.
Enfoque simple : para encontrar el piso de la raíz cuadrada, intente con números totalmente naturales a partir de 1. Continúe incrementando el número hasta que el cuadrado de ese número sea mayor que el número dado.

  • Algoritmo: 
    1. Crea una variable (contador) i y cuida algunos casos base, es decir, cuando el número dado es 0 o 1.
    2. Ejecute un ciclo hasta que i*i <= n , donde n es el número dado. Incrementa i en 1.
    3. El suelo de la raíz cuadrada del número es i – 1
  • Implementación:

C++

// A C++ program to find floor(sqrt(x)
#include<bits/stdc++.h>
using namespace std;
 
// Returns floor of square root of x
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
    return x;
 
    // Starting from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result <= x)
    {
      i++;
      result = i * i;
    }
    return i - 1;
}
 
// Driver program
int main()
{
    int x = 11;
    cout << floorSqrt(x) << endl;
    return 0;
}

C

#include <stdio.h>
 
// Returns floor of square root of x
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
    return x;
 
    // Starting from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result <= x)
    {
    i++;
    result = i * i;
    }
    return i - 1;
}
 
// Driver program
int main()
{
    int x = 11;
    printf("%d\n",floorSqrt(x));
  return 0;
}
//code is contributed by lalith kumar.g

Java

// A Java program to find floor(sqrt(x))
 
class GFG {
     
    // Returns floor of square root of x
    static int floorSqrt(int x)
    {
        // Base cases
        if (x == 0 || x == 1)
            return x;
 
        // Starting from 1, try all numbers until
        // i*i is greater than or equal to x.
        int i = 1, result = 1;
         
        while (result <= x) {
            i++;
            result = i * i;
        }
        return i - 1;
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int x = 11;
        System.out.print(floorSqrt(x));
    }
}
 
// This code is contributed by Smitha Dinesh Semwal.

Python3

# Python3 program to find floor(sqrt(x)
 
# Returns floor of square root of x
def floorSqrt(x):
 
    # Base cases
    if (x == 0 or x == 1):
        return x
 
    # Starting from 1, try all numbers until
    # i*i is greater than or equal to x.
    i = 1; result = 1
    while (result <= x):
     
        i += 1
        result = i * i
     
    return i - 1
 
# Driver Code
x = 11
print(floorSqrt(x))
 
# This code is contributed by Smitha Dinesh Semwal.

C#

// A C# program to
// find floor(sqrt(x))
using System;
 
class GFG
{
    // Returns floor of
    // square root of x
    static int floorSqrt(int x)
    {
        // Base cases
        if (x == 0 || x == 1)
            return x;
 
        // Starting from 1, try all
        // numbers until i*i is
        // greater than or equal to x.
        int i = 1, result = 1;
         
        while (result <= x)
        {
            i++;
            result = i * i;
        }
        return i - 1;
    }
 
    // Driver Code
    static public void Main ()
    {
        int x = 11;
        Console.WriteLine(floorSqrt(x));
    }
}
 
// This code is contributed by ajit

PHP

<?php
// A PHP program to find floor(sqrt(x)
 
// Returns floor of square root of x
function floorSqrt($x)
{
    // Base cases
    if ($x == 0 || $x == 1)
    return $x;
 
    // Starting from 1, try all
    // numbers until i*i is
    // greater than or equal to x.
    $i = 1;
    $result = 1;
    while ($result <= $x)
    {
        $i++;
        $result = $i * $i;
    }
    return $i - 1;
}
 
// Driver Code
$x = 11;
echo floorSqrt($x), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// A Javascript program to find floor(sqrt(x)
 
// Returns floor of square root of x
function floorSqrt(x)
{
     
    // Base cases
    if (x == 0 || x == 1)
        return x;
 
    // Starting from 1, try all
    // numbers until i*i is
    // greater than or equal to x.
    let i = 1;
    let result = 1;
     
    while (result <= x)
    {
        i++;
        result = i * i;
    }
    return i - 1;
}
 
// Driver Code
let x = 11;
document.write(floorSqrt(x));
 
// This code is contributed by mohan
 
</script>

Producción :

3
  • Análisis de Complejidad: 
    • Complejidad Temporal: O(√ n). 
      Solo se necesita un recorrido de la solución, por lo que la complejidad temporal es O(√ n).
    • Complejidad espacial: O(1). 
      Se necesita espacio adicional constante.

Gracias Fattepur Mahesh por sugerir esta solución.  
Mejor enfoque : la idea es encontrar el entero más grande i cuyo cuadrado sea menor o igual que el número dado. La idea es utilizar la búsqueda binaria para resolver el problema. Los valores de i * i aumentan monótonamente, por lo que el problema se puede resolver mediante la búsqueda binaria. 

  • Algoritmo: 
    1. Tenga cuidado con algunos casos base, es decir, cuando el número dado es 0 o 1.
    2. Cree algunas variables, límite inferior l = 0 , límite superior r = n , donde n es el número dado, mid y ans para almacenar la respuesta.
    3. Ejecute un ciclo hasta que l <= r , el espacio de búsqueda desaparezca
    4. Compruebe si el cuadrado de mid ( mid = (l + r)/2 ) es menor o igual que n. Si es así, busque un valor mayor en la segunda mitad del espacio de búsqueda, es decir, l = mid + 1, actualice ans = medio
    5. De lo contrario, si el cuadrado de mid es mayor que n, busque un valor más pequeño en la primera mitad del espacio de búsqueda, es decir, r = mid – 1
    6. Imprime el valor de la respuesta ( ans )
  • Implementación:

C++

#include <iostream>
 
using namespace std;
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
        return x;
 
    // Do Binary Search for floor(sqrt(x))
    int start = 1, end = x/2, ans;
    while (start <= end) {
        int mid = (start + end) / 2;
 
        // If x is a perfect square
        int sqr = mid * mid;
        if (sqr == x)
            return mid;
 
        // Since we need floor, we update answer when
        // mid*mid is smaller than x, and move closer to
        // sqrt(x)
 
        /*
           if(mid*mid<=x)
                   {
                           start = mid+1;
                           ans = mid;
                   }
            Here basically if we multiply mid with itself so
           there will be integer overflow which will throw
           tle for larger input so to overcome this
           situation we can use long or we can just divide
            the number by mid which is same as checking
           mid*mid < x
 
           */
        if (sqr <= x) {
            start = mid + 1;
            ans = mid;
        }
        else // If mid*mid is greater than x
            end = mid - 1;
    }
    return ans;
}
 
// Driver program
int main()
{
    int x = 20221;
    cout << floorSqrt(x) << endl;
    return 0;
}

C

#include <stdio.h>
#include <math.h>
 
 int floorSqrt(int x)
    {
        // Base Cases
        if (x == 0 || x == 1)
            return x;
 
 
        // Do Binary Search for floor(sqrt(x))
        long start = 1, end = x, ans=0;
        while (start <= end)
        {
            int mid = (start + end) / 2;
 
            // If x is a perfect square
            if (mid*mid == x)
                return (int)mid;
 
            // Since we need floor, we update answer when mid*mid is
            // smaller than x, and move closer to sqrt(x)
            if (mid*mid < x)
            {
                start = mid + 1;
                ans = mid;
            }
            else // If mid*mid is greater than x
                end = mid-1;
        }
        return (int)ans;
    }
 
    // Driver Method
    int main()
    {
        int x = 11;
        printf("%d\n",floorSqrt(x));
    }
 
//Contributed by lalith kumar.g

Java

// A Java program to find floor(sqrt(x)
public class Test
{
    public static int floorSqrt(int x)
    {
        // Base Cases
        if (x == 0 || x == 1)
            return x;
 
 
        // Do Binary Search for floor(sqrt(x))
        long start = 1, end = x, ans=0;
        while (start <= end)
        {
            long mid = (start + end) / 2;
 
            // If x is a perfect square
            if (mid*mid == x)
                return (int)mid;
 
            // Since we need floor, we update answer when mid*mid is
            // smaller than x, and move closer to sqrt(x)
            if (mid*mid < x)
            {
                start = mid + 1;
                ans = mid;
            }
            else   // If mid*mid is greater than x
                end = mid-1;
        }
        return (int)ans;
    }
 
    // Driver Method
    public static void main(String args[])
    {
        int x = 11;
        System.out.println(floorSqrt(x));
    }
}
// Contributed by InnerPeace

Python3

# Python 3 program to find floor(sqrt(x)
 
# Returns floor of square root of x        
def floorSqrt(x) :
 
    # Base cases
    if (x == 0 or x == 1) :
        return x
  
    # Do Binary Search for floor(sqrt(x))
    start = 1
    end = x  
    while (start <= end) :
        mid = (start + end) // 2
         
        # If x is a perfect square
        if (mid*mid == x) :
            return mid
             
        # Since we need floor, we update
        # answer when mid*mid is smaller
        # than x, and move closer to sqrt(x)
        if (mid * mid < x) :
            start = mid + 1
            ans = mid
             
        else :
             
            # If mid*mid is greater than x
            end = mid-1
             
    return ans
 
# driver code   
x = 11
print(floorSqrt(x))
     
# This code is contributed by Nikita Tiwari.

C#

// A C# program to
// find floor(sqrt(x)
using System;
 
class GFG
{
    public static int floorSqrt(int x)
    {
        // Base Cases
        if (x == 0 || x == 1)
            return x;
 
        // Do Binary Search
        // for floor(sqrt(x))
        int start = 1, end = x, ans = 0;
        while (start <= end)
        {
            int mid = (start + end) / 2;
 
            // If x is a
            // perfect square
            if (mid * mid == x)
                return mid;
 
            // Since we need floor, we
            // update answer when mid *
            // mid is smaller than x,
            // and move closer to sqrt(x)
            if (mid * mid < x)
            {
                start = mid + 1;
                ans = mid;
            }
             
            // If mid*mid is
            // greater than x
            else
                end = mid-1;
        }
        return ans;
    }
 
    // Driver Code
    static public void Main ()
    {
        int x = 11;
        Console.WriteLine(floorSqrt(x));
    }
}
 
// This code is Contributed by m_kit

PHP

<?php
// A PHP program to find floor(sqrt(x)
 
// Returns floor of
// square root of x        
function floorSqrt($x)
{
    // Base cases
    if ($x == 0 || $x == 1)
    return $x;
 
    // Do Binary Search
    // for floor(sqrt(x))
    $start = 1; $end = $x; $ans;
    while ($start <= $end)
    {
        $mid = ($start + $end) / 2;
 
        // If x is a perfect square
        if ($mid * $mid == $x)
            return $mid;
 
        // Since we need floor, we update
        // answer when mid*mid is  smaller
        // than x, and move closer to sqrt(x)
        if ($mid * $mid < $x)
        {
            $start = $mid + 1;
            $ans = $mid;
        }
         
        // If mid*mid is
        // greater than x
        else
            $end = $mid-1;    
    }
    return $ans;
}
 
// Driver Code
$x = 11;
echo floorSqrt($x), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
    // A Javascript program to find floor(sqrt(x)
 
// Returns floor of
// square root of x        
function floorSqrt(x)
{
    // Base cases
    if (x == 0 || x == 1)
    return x;
 
    // Do Binary Search
    // for floor(sqrt(x))
    let start = 1;
    let end = x;
    let ans;
    while (start <= end)
    {
        let mid = (start + end) / 2;
 
        // If x is a perfect square
        if (mid * mid == x)
            return mid;
 
        // Since we need floor, we update
        // answer when mid*mid is  smaller
        // than x, and move closer to sqrt(x)
        if (mid * mid < x)
        {
            start = mid + 1;
            ans = mid;
        }
         
        // If mid*mid is
        // greater than x
        else
            end = mid-1;    
    }
    return ans;
}
 
// Driver Code
let x = 11;
document.write(floorSqrt(x) +  "<br>");
 
// This code is contributed by _saurabh_jaiswal
</script>

Producción :

142
  • Análisis de Complejidad: 
    • Complejidad temporal: O(log n). 
      La complejidad temporal de la búsqueda binaria es O(log n).
    • Complejidad espacial: O(1). 
      Se necesita espacio adicional constante.

Gracias a Gaurav Ahirwar por sugerir el método anterior.
Nota: La búsqueda binaria se puede optimizar aún más para comenzar con ‘inicio’ = 0 y ‘fin’ = x/2. El suelo de la raíz cuadrada de x no puede ser mayor que x/2 cuando x > 1.
Gracias a la visita por sugerir la optimización anterior.

Mejor enfoque: la lógica es simple, ya que podemos observar que para un número cuadrado perfecto, su raíz cuadrada representa el número total del cuadrado perfecto de 1 a x .

por ejemplo:- sqrt(1)=1, sqrt(4)=2, sqrt(9)=3 …….. y así sucesivamente.

  • Algoritmo:

                            1. encuentre la raíz cuadrada de x y guárdela en una variable sqrt.

                            2. Use el valor mínimo de sqrt y guárdelo en resultado variable, porque para un número cuadrado no perfecto. su valor mínimo da el resultado.

                            3. devolver el resultado.

  • Implementación:

C++

#include <bits/stdc++.h>
using namespace std;
int countSquares(int x)
{
    int sqr = sqrt(x);
    int result = (int)(sqr);
    return result;
}
int main()
{
 
    int x = 9;
    cout << (countSquares(x));
 
    return 0;
}
 
// This code is contributed by Rajput-Ji

C

#include <stdio.h>
#include <math.h>
 
    static int countSquares(int x) {
        int sqr = (int) sqrt(x);
        int result = (int) (sqr);
        return result;
    }
 
int main()
    {
        int x = 9;
        printf("%d\n",countSquares(x));
    }
// This code is contributed by lalith kumar.g

Java

import java.util.*;
 
class GFG {
    static int countSquares(int x) {
        int sqr = (int) Math.sqrt(x);
        int result = (int) (sqr);
        return result;
    }
 
    public static void main(String[] args)
    {
        int x = 9;
        System.out.print(countSquares(x));
    }
}
 
// This code is contributed by Rajput-Ji

Python3

def countSquares(x):
  sqrt = x**0.5
  result = int(sqrt)
  return result
x = 9
print(countSquares(x))

C#

using System;
public class GFG {
  static int countSquares(int x) {
    int sqr = (int) Math.Sqrt(x);
    int result = (int) (sqr);
    return result;
  }
 
  public static void Main(String[] args) {
    int x = 9;
    Console.Write(countSquares(x));
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
    function countSquares(x) {
        var sqr = parseInt( Math.sqrt(x));
        var result = parseInt(sqr);
        return result;
    }
 
        var x = 9;
        document.write(countSquares(x));
 
// This code is contributed by Rajput-Ji
</script>

Producción:

3

Complejidad temporal: O(log n)
Espacio auxiliar: O(1)

Método:   Encontrar la raíz cuadrada de un número entero usando la función sqrt() del módulo matemático.

Python3

# Python3 program to find (sqrt(x))
from math import*
n=4
# using the sqrt function of math
# module finding the square root integer
print(round(sqrt(n)))
 
# This code is contributed by gangarajula laxmi
Producción

2
  • Análisis de Complejidad
    • Complejidad de tiempo: – O (log n)
    • Espacio Auxiliar :-   O(1)
       

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *