Can Anyone explain what is the precision error in Java

Блог пользователя ChatGPT-4o-mini

Автор ChatGPT-4o-mini, история, 2 года назад, По-английски

While solving problem B in Codeforces Round 976 when I was calculating my answer I was using the square root function to calculate

import java.util.Scanner;

public class Main {

static Scanner sc = new Scanner(System.in);

static long f(long mid) {
    long t = (long) Math.sqrt(mid);
    return mid - t;
}

static void solve() {
    long k = sc.nextLong();
    long l = 1, r = (long) 5e18;
    long ans = 0;

    while (l <= r) {
        long mid = (l + r) / 2;
        if (f(mid) >= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    System.out.println(ans);
}

public static void main(String[] args) {

    int t = sc.nextInt();
    while (t-- > 0) {
        solve();
    }
    sc.close();
}

}

but it was giving WA on test case on k = 854258779689358055

instead when I wrote the same code in C++ and submitted it , it gave AC....Could anyone tellme why that happened...

283627551

Help please...

ChatGPT-4o-mini
2 года назад
4

Комментарии (4)

Написать комментарий?

MainFrame_KuznetSov

2 года назад, скрыть # |

← Rev. 2 →

Change first line of the while loop:-

mid=L+(R-L)/2

You are experiencing the error because for worst case R=5e18 and L=5e18-1 So L+R=1e19-1 which exceeds the max value of long(9e18) and hence gives a faulty value(possibly -9e18 or something).

Hope this helped you (-:

→ Ответить

ChatGPT-4o-mini

2 года назад, скрыть # ^ |

It is still giving WA

→ Ответить

OneBased

2 года назад, скрыть # ^ |

← Rev. 4 →

You should always use sqrtl instead of sqrt because of precision issues.

Here is the equivalent

static long sqrtl(long x) {

long sq = (long) Math.sqrt(x);  // Take the integer part of the square root

    if (sq * sq > x) return sq - 1; // Ensure we don't overshoot the correct integer

    return sq;
}

Hope this helps

→ Ответить