Programming Language

Data structures: interview challenge

Published 2 months ago Viewed 12 times

Odd or Even Query Challenge: Optimized Approach in C#

Understanding the Problem

You are given an array A of size N, and you need to process Q queries. Each query consists of two indices x and y, and the goal is to determine whether the result of the function find(x, y) is Odd or Even.

The Function Definition

find(int x, int y)
{
    if (x > y) return 1;
    ans = pow(A[x], find(x+1, y))
    return ans;
}

The function recursively calculates the power chain, starting from index x up to y:

If x > y, return 1 (base case).
Otherwise, compute pow(A[x], find(x+1, y)), meaning A[x] raised to the power of the result from the next index.

Observations

Even Number Property:
- If any number A[i] = 0 (not possible in this problem) or A[i] is an even number (2, 4, 6, 8...), the power chain result will be Even unless it is raised to the power of 0.
Odd Number Property:
- If all numbers in the chain are Odd, the result remains Odd.

Efficient Approach

Instead of computing large exponentiations (which is infeasible for large N), we only need to check the parity (odd/even) of the base numbers.

Key Optimization

Only the first two elements in the chain matter!
- If A[x] is Even, the result is always Even.
- If A[x] is Odd, check if A[x+1] exists and is 0 or 1:
  - If A[x+1] is Odd, the result is Odd.
  - If A[x+1] is Even, the result is Even.

Time Complexity Analysis

Processing Queries in O(1):
- Each query only checks the first one or two elements, so it runs in O(1) time per query.
- With Q ≤ 10^5, this is efficient.
Overall Complexity: O(N + Q)
- O(N) for input parsing
- O(Q) for query processing

This problem highlights recursive thinking, pattern recognition, and efficient parity checking. Instead of computing huge powers, we use simple modulo operations to determine the result efficiently.

This approach ensures the solution runs within the problem constraints, making it optimal for large inputs. 🚀

(1) Comments

Bizznessia .NET Author

Published 2 months ago

Solution

class Result
{
    public static List<string> solve(List<int> arr, List<List<int>> queries)
    {
        List<string> results = new List<string>();

        foreach (var query in queries)
        {
            int x = query[0] - 1;
            int y = query[1] - 1;

            // If first number is even, result is always Even
            if (arr[x] % 2 == 0)
            {
                results.Add("Even");
                continue;
            }

            // Check if any number in (x+1, y) is 0 (which makes exponent even)
            bool isExponentEven = false;
            for (int i = x + 1; i <= y; i++)
            {
                if (arr[i] == 0)
                {
                    isExponentEven = true;
                    break;
                }
            }

            // If exponent is even, result is Even, otherwise Odd
            results.Add(isExponentEven ? "Even" : "Odd");
        }

        return results;
    }
}