✏️ Задачка с собеса

Дано целое число, нужно проверить, является ли оно полным квадратом.

Первый рефлекс новичка — взять квадратный корень и проверить, целое ли число:

(int)Math.Sqrt(num) * (int)Math.Sqrt(num) == num

Но на собесе после этого последует вопрос: «А можете без встроенной функции?» Вот тогда начинается интересное.

Вместо математики используем логику: если x * x = num, то x находится где-то между 1 и num. Сужаем диапазон поиска, пока не найдём точный ответ.

public bool IsPerfectSquare(int num)
{
    long left = 1;
    long right = num;
    
    while (left <= right)
    {
        long mid = (left + right) / 2;
        long square = mid * mid;
        
        if (square == num)
            return true;
        else if (square < num)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return false;
}

Есть ещё метод Ньютона для поиска корня — он даже быстрее для больших чисел:

public bool IsPerfectSquare(int num)
{
    long x = num;
    
    while (x * x > num)
    {
        x = (x + num / x) / 2;
    }
    
    return x * x == num;
}

Главное: объясните почему вы выбрали именно этот подход, а не просто скопировали решение. На собесе вас оценивают не только по скорости, а по способности мыслить.

➡️ Попробовать решить

🐸Библиотека шарписта

#dotnet_challenge