Faulty Sensor

🏠 ⬅️ ➡️

An experiment is being conducted in a lab. To ensure accuracy, there are two sensors collecting data simultaneously. You are given two arrays sensor1 and sensor2, where sensor1[i] and sensor2[i] are the ith data points collected by the two sensors.

However, this type of sensor has a chance of being defective, which causes exactly one data point to be dropped. After the data is dropped, all the data points to the right of the dropped data are shifted one place to the left, and the last data point is replaced with some random value. It is guaranteed that this random value will not be equal to the dropped value.

  • For example, if the correct data is [1,2,**3**,4,5] and 3 is dropped, the sensor could return [1,2,4,5,**7**] (the last position can be any value, not just 7).

We know that there is a defect in at most one of the sensors. Return the sensor number (1 or 2) with the defect. If there is no defect in either sensor or if it is impossible to determine the defective sensor, return -1.

Example 1:

Input: sensor1 = [2,3,4,5], sensor2 = [2,1,3,4] Output: 1 Explanation: Sensor 2 has the correct values. The second data point from sensor 2 is dropped, and the last value of sensor 1 is replaced by a 5.

Example 2:

Input: sensor1 = [2,2,2,2,2], sensor2 = [2,2,2,2,5] Output: -1 Explanation: It is impossible to determine which sensor has a defect. Dropping the last value for either sensor could produce the output for the other sensor.

Example 3:

Input: sensor1 = [2,3,2,2,3,2], sensor2 = [2,3,2,3,2,7] Output: 2 Explanation: Sensor 1 has the correct values. The fourth data point from sensor 1 is dropped, and the last value of sensor 1 is replaced by a 7.

Constraints:

  • sensor1.length == sensor2.length
  • 1 <= sensor1.length <= 100
  • 1 <= sensor1[i], sensor2[i] <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k
    integer, parameter :: n = 5
    integer, dimension(n) :: sensor1, sensor2
    integer :: result

    ! Example 1
    sensor1 = [2, 3, 4, 5]
    sensor2 = [2, 1, 3, 4]
    write(*,*) 'Example 1:'
    write(*,*) 'Sensor 1:', sensor1
    write(*,*) 'Sensor 2:', sensor2
    result = solve(sensor1, sensor2)
    write(*,*) 'Result: ', result

    ! Example 2
    sensor1 = [2, 2, 2, 2, 2]
    sensor2 = [2, 2, 2, 2, 5]
    write(*,*) 'Example 2:'
    write(*,*) 'Sensor 1:', sensor1
    write(*,*) 'Sensor 2:', sensor2
    result = solve(sensor1, sensor2)
    write(*,*) 'Result: ', result

    ! Example 3
    sensor1 = [2, 3, 2, 2, 3, 2]
    sensor2 = [2, 3, 2, 3, 2, 7]
    write(*,*) 'Example 3:'
    write(*,*) 'Sensor 1:', sensor1
    write(*,*) 'Sensor 2:', sensor2
    result = solve(sensor1, sensor2)
    write(*,*) 'Result: ', result

contains

    function solve(sensor1, sensor2) result(result)
        implicit none
        integer, intent(in) :: sensor1(:), sensor2(:)
        integer :: result

        do i = 1, size(sensor1)
            if (sensor1(i) /= sensor2(i)) then
                exit
            end if
        end do

        if (i > size(sensor1)) then
            result = -1
        else
            result = mod(i, 2) + 1
        end if

    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

integer, parameter :: dp = selected_real_kind(15, 307)

integer :: i, j, k, l, m, n
integer :: sensor1(100), sensor2(100)
integer :: sensor_with_defect

! Example 1
sensor1 = [2,3,4,5]
sensor2 = [2,1,3,4]

! Example 2
!sensor1 = [2,2,2,2,2]
!sensor2 = [2,2,2,2,5]

! Example 3
!sensor1 = [2,3,2,2,3,2]
!sensor2 = [2,3,2,3,2,7]

! Initialize the sensor with the defect
sensor_with_defect = -1

! Check if the sensors are equal
do i = 1, size(sensor1)
    if (sensor1(i) /= sensor2(i)) then
        sensor_with_defect = i
        exit
    end if
end do

! Print the result
if (sensor_with_defect == -1) then
    print *, "No defect in either sensor"
else
    print *, "Sensor with defect: ", sensor_with_defect
end if

end module
🌐 Data from online sources 
def maximizeXor(nums, queries):
    trie = {}
    nums.sort()

    new_queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda x: x[1])

    ans = [0] * len(queries)

    idx = 0
    for x, m, i in new_queries:
        while idx < len(nums) and nums[idx] <= m:
            t = nums[idx]
            idx += 1
            cur = trie
            for j in range(31, -1, -1):
                bit = (t >> j) & 1
                cur = cur.setdefault(bit, {})
        cur = trie
        xor_value = 0
        for j in range(31, -1, -1):
            bit = (x >> j) & 1
            if 1 ^ bit in cur:
                cur = cur[1 ^ bit]
                xor_value |= 1 << j
            else:
                cur = cur[bit]
        ans[i] = xor_value if cur else -1

    return ans

The algorithm uses a Trie data structure to store the binary representation of numbers in the nums array.
  1. First, sort the nums array in ascending order.
  2. Create a new queries array, adding the index to each query, and sort according to the mi value.
  3. Iterate through the sorted queries array and update Trie with nums elements that are less than or equal to mi.
  4. For each x in the query, traverse the Trie and find the highest XOR value achievable.
  5. If there are no Trie nodes, set the answer to -1 for that query.
  6. Store the answer of each query in the ans array at the index originally present in the original query array.
  7. Return the ans array containing the answer to all queries.
🌐 Data from online sources 
#include <vector>
#include <algorithm>
using namespace std;

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < queries.size(); ++i) {
        queries[i].push_back(i);
    }
    sort(queries.begin(), queries.end(), [](vector<int> &a, vector<int> &b) {
        return a[1] < b[1];
    });

    vector<int> ans(queries.size());
    int idx = 0, trie[200010][2] = {}, sum[200010] = {1}, cnt = 0;
    for (const auto &q : queries) {
        int x = q[0], m = q[1], k = q[2], p = 0;
        while (idx < nums.size() && nums[idx] <= m) {
            int cur = 0, t = nums[idx++];
            for (int i = 31; i >= 0; --i) {
                int bit = ((t >> i) & 1);
                if (!trie[cur][bit]) {
                    trie[cur][bit] = ++cnt;
                }
                cur = trie[cur][bit];
            }
            sum[cur]++;
        }
        if (!cnt) { 
            ans[k] = -1; 
            continue; 
        }
        int cur = 0, ans2 = 0;
        for (int i = 31; i >= 0; --i) {
            int bit = ((x >> i) & 1);
            if (trie[cur][bit ^ 1]) {
                cur = trie[cur][bit ^ 1];
                ans2 |= (1 << i);
            } else {
                cur = trie[cur][bit];
            }
        }
        ans[k] = ans2;
    }
    return ans;
}

The algorithm uses a Trie data structure to store the binary representation of numbers in the nums array.
  1. First, sort the nums array in ascending order.
  2. Create a new queries array, adding the index to each query, and sort according to the mi value.
  3. Iterate through the sorted queries array and update Trie with nums elements that are less than or equal to mi.
  4. For each x in the query, traverse the Trie and find the highest XOR value achievable.
  5. If there are no Trie nodes, set the answer to -1 for that query.
  6. Store the answer of each query in the ans array at the index originally present in the original query array.
  7. Return the ans array containing the answer to all queries.