Member Avatar for Muhammad Arslan_1

Write a program to find the integer square root of a given number.That is the largest integer whose square is less than or equal to the given number.

  • 4 Contributors
  • 5 Replies
  • 223 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by mabdullah4

Dani AI

Generated

Clarification: the integer square root of a non-negative integer N is the largest integer r such that r*r <= N. asked for that; suggested using the floating-point sqrt approach and posted a brute-force loop. Both can work for small inputs, but the common pitfalls are floating-point rounding (casting a double can give the wrong integer for very large N), the brute-force loop being slow for big N, and portability issues like system("pause").

A robust, exam-friendly approach is an integer binary search: O(log N) time, no floating-point, and avoid overflow by testing mid > n / mid instead of computing mid * mid directly. The implementation below uses 64-bit integers and handles 0 and 1 as special cases.

#include <iostream>

using namespace std;

long long int_sqrt(long long n) {
    if (n < 0) return -1;        // undefined for negatives
    if (n < 2) return n;         // 0 and 1
    long long lo = 1, hi = n / 2, ans = 1;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (mid > n / mid) {    // avoids mid*mid overflow
            hi = mid - 1;
        } else {
            ans = mid;
            lo = mid + 1;
        }
    }
    return ans;
}

int main() {
    long long n;
    if (!(cin >> n)) return 0;
    cout << int_sqrt(n) << '\n';
    return 0;
}

Notes: for contest/exam code avoid system("pause"); return appropriate values for invalid input (here -1 for negatives); if using sqrt from <cmath> as a shortcut, always verify the integer result by checking (r+1)*(r+1) <= n and r*r > n to correct any rounding. This binary-search method is fast, simple to reason about, and safe for large 64-bit inputs.

Recommended Answers

All 5 Replies

Member Avatar for JamesCherrill

OK, I've written it. If you let me have your teacher's email address I can submit it for you to save you the bother of copy/pasting it yourself.

DaniWeb Member Rules (which you agreed to when you signed up) include:
"Do provide evidence of having done some work yourself if posting questions from school or work assignments"
http://www.daniweb.com/community/rules

Member Avatar for Muhammad Arslan_1

this is not my assignment .i am actually want to preparing for exams but this question is very tough for me and in previous year this question had been asked .SO this is very important question Please Help BROTHER!!!!

Member Avatar for AssertNull

Use the sqrt function from the cmath library. That gives you a double as an answer. Assign it to an integer variable.

int x = sqrt(24); // x = 4
Member Avatar for JamesCherrill

Just giving you the code isn't going to help your ability. Memorising answers to possible questions is no way to improve, it's just a dead-end. If you want to do better in the exams then improve your programming skills by trying to code this yourself. If you try, and get stuck, then come back here and someone will help.

Member Avatar for mabdullah4 
//Hope this Helps

#include<iostream>
using namespace std;
int main()
{
    int i=1,y=0,x=1;
    int number=0;
    cout<<"Enter Number to Find Square Root ";
    cin>>number;

    for(i=1;i*i<=number;i=i+1)
    {
        y=i*i;

        x = (i+1) * (i+1);
        if(x>number)
        {
            break;
        }

    }
    cout<<"The Square of the Number is "<<i<<endl;
    system("pause");

}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.