Decode XORed Array

🏠 ⬅️ ➡️

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1 Output: [1,0,2,1] Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2:

Input: encoded = [6,2,7,3], first = 4 Output: [4,2,0,7,4]

Constraints:

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n) :: arr
    integer, dimension(n - 1) :: encoded
    integer :: first

    ! Examples
    encoded = [1, 2, 3]
    first = 1
    call solve(encoded, first, arr)
    write (*, '(A)') 'Example 1:'
    write (*, '(A)') 'encoded = [1,2,3]'
    write (*, '(A)') 'first = 1'
    write (*, '(A)') 'arr = [1,0,2,1]'
    write (*, '(A)') ''
    write (*, '(A)') 'Example 2:'
    write (*, '(A)') 'encoded = [6,2,7,3]'
    write (*, '(A)') 'first = 4'
    write (*, '(A)') 'arr = [4,2,0,7,4]'

contains

    subroutine solve(encoded, first, arr)
        implicit none
        integer, intent(in) :: encoded(:), first
        integer, intent(out) :: arr(:)

        integer :: i, j

        arr(1) = first
        do i = 2, size(arr)
            arr(i) = arr(i - 1) ^ encoded(i - 2)
        end do
    end subroutine solve

end program main
✅ Compiled
✅ Executed
❌ Correct 
module solution
    implicit none
    contains
    function decode(encoded, first) result(arr)
        integer, intent(in) :: encoded(:), first
        integer :: arr(size(encoded) + 1)
        arr(1) = first
        arr(2:) = encoded
    end function decode
end module solution

program main
    use solution
    implicit none
    integer, parameter :: n = 5
    integer :: encoded(n - 1) = [6, 2, 7, 3]
    integer :: first = 4
    integer :: arr(n)

    arr = decode(encoded, first)

    write (*, '(A, 5I5)') 'Original array:', arr
end program main
🌐 Data from online sources 
def minOperations(logs):
    depth = 0
    for log in logs:
        if log == "../":
            if depth > 0:
                depth -= 1
        elif log != "./":
            depth += 1
    return depth

The algorithm maintains a variable `depth` to keep track of the current folder depth from the main folder. It starts from 0 (main folder) becuase the file system initially starts in the main folder. Then, it iterates through the `logs` list:
  • If the log is "../", it means the operation is to go up one level, so we decrement the depth by 1. Note that we check if depth is greater than 0 to handle the situation where the current folder is already the main folder (we don't want to go above the main folder).
  • If the log is not "./" (which means it's a sub-folder), it means the operation is to go down one level, so we increment the depth by 1.

After the loop, the value of depth represents the minimum number of operations needed to go back to the main folder, so we return it.

🌐 Data from online sources 
int minOperations(vector<string>& logs) {
    int depth = 0;
    for (const string& log : logs) {
        if (log == "../") {
            if (depth > 0) {
                depth--;
            }
        } else if (log != "./") {
            depth++;
        }
    }
    return depth;
}

The algorithm maintains a variable `depth` to keep track of the current folder depth from the main folder. It starts from 0 (main folder) becuase the file system initially starts in the main folder. Then, it iterates through the `logs` list:
  • If the log is "../", it means the operation is to go up one level, so we decrement the depth by 1. Note that we check if depth is greater than 0 to handle the situation where the current folder is already the main folder (we don't want to go above the main folder).
  • If the log is not "./" (which means it's a sub-folder), it means the operation is to go down one level, so we increment the depth by 1.

After the loop, the value of depth represents the minimum number of operations needed to go back to the main folder, so we return it.