# 13.03.2024 [2485. Find the Pivot Integer]
Pivot of `1..n` where `sum[1..p] == sum[p..n]`. #easy
13.03.2024
2485. Find the Pivot Integer easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/537
Problem TLDR
Pivot of 1..n
where sum[1..p] == sum[p..n]
. #easy
Intuition
Let’s observe an example:
// 1 2 3 4 5 6 7 8
// 1 2 3 4 5 5 * 6 / 2 = 15
// 6 7 8 8 * 9 / 2 = 36 - 15
// p=6
// p * (p + 1) / 2 == n * (n + 1) / 2 - p * (p - 1) / 2
The left part will increase with the grown of pivot p
, so we can use Binary Search in that space.
Another solution is to simplify the equation more:
// x(x + 1)/2 == n(n + 1)/2 - x(x + 1)/2 + x
// x(x + 1) - x == sum
// x^2 == sum
Given that, just check if square root is perfect.
Approach
For more robust Binary Search:
use inclusive
lo
andhi
check the last condition
lo == hi
always move the boundaries:
lo = mi + 1
,hi = mid -
use a separate condition to exit
Complexity
Time complexity:
O(log(n)), square root is also log(n)Space complexity:
O(1)
Code
fun pivotInteger(n: Int): Int {
var lo = 1; var hi = n;
while (lo <= hi) {
val p = lo + (hi - lo) / 2
val l = p * (p + 1) / 2
val r = n * (n + 1) / 2 - p * (p - 1) / 2
if (l < r) lo = p + 1 else
if (l > r) hi = p - 1 else return p
}
return -1
}
pub fn pivot_integer(n: i32) -> i32 {
let sum = n * (n + 1) / 2;
let sq = (sum as f32).sqrt() as i32;
if (sq * sq == sum) { sq } else { -1 }
}