Niloy007

Count Squares

Mar 18th, 2021
584
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // { Driver Code Starts
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6.  // } Driver Code Ends
  7.  
  8. class Solution {
  9.   public:
  10.  
  11.     int bisection(double x) {
  12.         double l = 0, r = x, mid;
  13.         int count = 64;
  14.    
  15.         while (count--) {
  16.             mid = (l + r) / 2.0;
  17.             if (mid * mid == x) {
  18.                 return mid;
  19.             }
  20.             if ((mid * mid) < x) {
  21.                 l = mid;
  22.             } else {
  23.                 r = mid;
  24.             }
  25.         }
  26.         return floor(mid);
  27.     }
  28.    
  29.    
  30.     int countSquares(int N) {
  31.         // code here
  32.         int n;
  33.         cin >>
  34.         int res = bisection(n - 1);
  35.    
  36.         int count = 0;
  37.         for (int i = 1; i <= res; i++) {
  38.             if (pow(i, 2) < n) {
  39.                 count++;
  40.             }
  41.         }
  42.         return count;
  43.        
  44.     }
  45. };
  46.  
  47. // { Driver Code Starts.
  48. int main() {
  49.     int t;
  50.     cin >> t;
  51.     while (t--) {
  52.         int N;
  53.        
  54.         cin>>N;
  55.  
  56.         Solution ob;
  57.         cout << ob.countSquares(N) << endl;
  58.     }
  59.     return 0;
  60. }  // } Driver Code Ends
RAW Paste Data