Introduction

In this blog post, we will explore how to solve the LeetCode problem "1346" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given an array arr of integers, check if there exist two indices i and j such that : i != j 0 <= i, j < arr.length arr[i] == 2 arr[j] Example 1: Input: arr = [10,2,5,3] Output: true Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 5 == 2 * arr[j] Example 2: Input: arr = [3,1,7,11] Output: false Explanation: There is no i and j that satisfy the conditions. Constraints: 2 <= arr.length <= 500 -103 <= arr[i] <= 103

Explanation

Here's the solution to the problem, explained with high-level approach, complexity analysis, and the Python code.

• High-Level Approach:

  • Use a hash set (or dictionary) to store each number encountered in the array.
  • Iterate through the array: for each number num, check if 2 * num or num / 2 exists in the hash set. If either exists (and num/2 is an integer), return true.
  • If the loop completes without finding such a pair, return false.

• Complexity Analysis:

  • Runtime Complexity: O(n), where n is the length of the array. This is because we iterate through the array once. Hash set lookups take O(1) on average.
  • Storage Complexity: O(n), as we store, at most, n elements in the hash set.

Code

    def checkIfExist(arr):
    """
    Given an array arr of integers, check if there exist two indices i and j such that :
    i != j
    0 <= i, j < arr.length
    arr[i] == 2 * arr[j]

    Example 1:
    Input: arr = [10,2,5,3]
    Output: true
    Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

    Example 2:
    Input: arr = [3,1,7,11]
    Output: false
    Explanation: There is no i and j that satisfy the conditions.

    Constraints:
    2 <= arr.length <= 500
    -10^3 <= arr[i] <= 10^3
    """
    seen = set()
    for num in arr:
        if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
            return True
        seen.add(num)
    return False