2485 - Find the Pivot Integer (Easy)
Problem Link
https://leetcode.com/problems/find-the-pivot-integer/
Problem Statement
Given a positive integer n, find the pivot integer x such that:
The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively. Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.
Example 1:
Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.Example 2:
`` Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1.
**Example 3:**
Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.
**Constraints**:
- 1 <= n <= 1000Approach 1: Math
-
Time Complexity:
-
Space Complexity:
class Solution {
public:
int pivotInteger(int n) {
int s1 = n * (n + 1) / 2, s2 = 0;
for (int i = 1; i <= n; i++) {
s2 += i;
if (s1 == s2) return i;
s1 -= i;
}
return -1;
}
};Approach 2: Binary Search
-
Time Complexity:
-
Space Complexity:
static int fast_io = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();
class Solution {
public:
__attribute__((disable_sanitizer_instrumentation))
static int pivotInteger(const int n) {
const int total = n * (n + 1) / 2;
int lo = 1;
int hi = n;
while (lo <= hi) {
const int x = lo + (hi - lo) / 2;
const int below = (x - 1) * x / 2;
const int left = below + x;
const int right = total - below;
if (left == right) {
return x;
} else if (left < right) {
lo = x + 1;
} else {
hi = x - 1;
}
}
return -1;
}
};2482 - Difference Between Ones and Zeros in Row and Column (Medium)
Author: @heder | https://leetcode.com/problems/difference-between-ones-and-zeros-in-row-and-column/
2486 - Append Characters to String to Make Subsequence (Medium)
Author: @dhanu084 | https://leetcode.com/problems/append-characters-to-string-to-make-subsequence/