Minimum Reverse Operations : Once upon a time, there was a magical array called “A.” This array had lots of zeros, but it had one special number: the number 1. The number 1 could move around in this array, but it had some rules to follow.
Rule 1: The 1 could do a special trick called an “operation.” This operation let the 1 pick a group of numbers in the array and flip them around. Imagine flipping pancakes in a pan! 🥞
Rule 2: The 1 couldn’t move to certain spots in the array. We called these spots “banned” because they were off-limits for the 1. 🚫
Now, we had to figure out how many operations the 1 needed to move to different places in the array, starting from a special spot called “p.”
To do this, we played a game using a magical tool called “BFS” (Breadth-First Search). Imagine it like going on a treasure hunt! 🗺️
Read More : Leet code : Reverse Linked List 206
Here’s how we played the game:
- We started at spot “p” where the 1 was already sitting. We put a flag there and said, “This is where the 1 starts and it took 0 operations.”
- We looked around and saw which spots the 1 could reach with one operation. These spots were like the next steps on our treasure map!
- We marked those spots with flags too, saying how many operations it took to reach them.
- Then, we looked at those newly marked spots and found where they could go in one more operation. We kept doing this until we couldn’t find any more new spots to explore.
- If we ever found a banned spot or a spot that we already visited, we didn’t go there again. We wanted to avoid those places!
- We kept playing until we explored all the possible spots, and we counted how many operations it took to reach each one.
- Finally, we had our answers! We knew how many operations the 1 needed to move to every spot in the array.
Leet Code : Reverse Nodes in k-Group Java, Python ,C++ JavaScript Solution
And that’s how we solved the magical array puzzle! 🧙♂️ We used a fun game called BFS to find the best way for the 1 to move around without going to banned spots. It was like going on an adventure to discover the treasure of answers! 🏴☠️
So, that’s the story of how we solved the problem, and now we have all the answers we need. The end! 🌟
Leet code :Zigzag Conversion solution c++ , Java , Python , JavaScript , Swift ,TypeScript
C++ Solution
#include <vector>
#include <set>
#include <queue>
using namespace std;
class Solution {
public:
pair<int, int> getRange(int x, int n, int k) {
int l = max(x - k + 1, 0), r = min(x, n - k);
int L = 2 * l + k - 1 - x, R = 2 * r + k - 1 - x;
return { L, R };
}
vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
set<int> even_indices, odd_indices;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
even_indices.insert(i);
} else {
odd_indices.insert(i);
}
}
for (int b : banned) {
if (b % 2 == 0) {
even_indices.erase(b);
} else {
odd_indices.erase(b);
}
}
vector<int> ans(n, -1);
queue<int> q;
q.push(p);
ans[p] = 0;
if (p % 2 == 0) {
even_indices.erase(p);
} else {
odd_indices.erase(p);
}
while (!q.empty()) {
int x = q.front();
q.pop();
pair<int, int> range = getRange(x, n, k);
set<int>& current_set = (range.first % 2 == 0) ? even_indices : odd_indices;
auto it = current_set.lower_bound(range.first);
while (it != current_set.end() && *it <= range.second) {
ans[*it] = ans[x] + 1;
q.push(*it);
it = current_set.erase(it);
}
}
return ans;
}
};
Leet Code : Maximum Score from Performing Multiplication Operations Cpp | Java | Python solution
Java Solution
import java.util.*;
class Solution {
public int[] minReverseOperations(int n, int p, int[] banned, int k) {
Set<Integer> evenIndices = new HashSet<>();
Set<Integer> oddIndices = new HashSet<>();
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
evenIndices.add(i);
} else {
oddIndices.add(i);
}
}
for (int b : banned) {
if (b % 2 == 0) {
evenIndices.remove(b);
} else {
oddIndices.remove(b);
}
}
int[] ans = new int[n];
Arrays.fill(ans, -1);
Queue<Integer> queue = new LinkedList<>();
queue.offer(p);
ans[p] = 0;
if (p % 2 == 0) {
evenIndices.remove(p);
} else {
oddIndices.remove(p);
}
while (!queue.isEmpty()) {
int x = queue.poll();
int[] range = getRange(x, n, k);
Set<Integer> currentSet = (range[0] % 2 == 0) ? evenIndices : oddIndices;
Iterator<Integer> iterator = currentSet.iterator();
while (iterator.hasNext()) {
int y = iterator.next();
if (y > range[1]) {
break;
}
ans[y] = ans[x] + 1;
queue.offer(y);
iterator.remove();
}
}
return ans;
}
private int[] getRange(int x, int n, int k) {
int l = Math.max(x - k + 1, 0);
int r = Math.min(x, n - k);
int L = 2 * l + k - 1 - x;
int R = 2 * r + k - 1 - x;
return new int[]{L, R};
}
}
Infosys and TCS Aptitude and logical reasoning question set 2 | Company wise Question
Python Solution
from collections import deque
class Solution:
def getRange(self, x, n, k):
l = max(x - k + 1, 0)
r = min(x, n - k)
L = 2 * l + k - 1 - x
R = 2 * r + k - 1 - x
return (L, R)
def minReverseOperations(self, n, p, banned, k):
even_indices = set(range(0, n, 2))
odd_indices = set(range(1, n, 2))
for b in banned:
if b % 2 == 0:
even_indices.discard(b)
else:
odd_indices.discard(b)
ans = [-1] * n
queue = deque()
queue.append(p)
ans[p] = 0
if p % 2 == 0:
even_indices.discard(p)
else:
odd_indices.discard(p)
while queue:
x = queue.popleft()
L, R = self.getRange(x, n, k)
current_set = even_indices if L % 2 == 0 else odd_indices
iterator = iter(current_set)
while iterator:
y = next(iterator, None)
if y is None or y > R:
break
ans[y] = ans[x] + 1
queue.append(y)
iterator = current_set.discard(y)
return ans
Javascript Solution
class Solution {
getRange(x, n, k) {
const l = Math.max(x - k + 1, 0);
const r = Math.min(x, n - k);
const L = 2 * l + k - 1 - x;
const R = 2 * r + k - 1 - x;
return [L, R];
}
minReverseOperations(n, p, banned, k) {
const evenIndices = new Set(Array.from({ length: n }, (_, i) => i).filter(i => i % 2 === 0));
const oddIndices = new Set(Array.from({ length: n }, (_, i) => i).filter(i => i % 2 !== 0));
for (const b of banned) {
if (b % 2 === 0) {
evenIndices.delete(b);
} else {
oddIndices.delete(b);
}
}
const ans = new Array(n).fill(-1);
const queue = [];
queue.push(p);
ans[p] = 0;
if (p % 2 === 0) {
evenIndices.delete(p);
} else {
oddIndices.delete(p);
}
while (queue.length > 0) {
const x = queue.shift();
const [L, R] = this.getRange(x, n, k);
const currentSet = (L % 2 === 0) ? evenIndices : oddIndices;
for (const y of currentSet) {
if (y > R) {
break;
}
ans[y] = ans[x] + 1;
queue.push(y);
currentSet.delete(y);
}
}
return ans;
}
}
`