Count Valid Square Pairs
Updated
Problem statement
You are given an integer array nums.
A pair of indices (i, j) is valid when both of these hold:
i < jnums[i] == nums[j] * nums[j]
In other words, the earlier number must equal the square of the later number.
Return the number of valid pairs.
Function
countValidPairs(nums: int[]) → longExamples
Example 1
nums = [4,2,9,3,4,-2]return = 4The valid pairs are (0, 1), (0, 5), (2, 3) and (4, 5).
4 == 2 * 2 and 4 == (-2) * (-2), so the 4 at index 0 pairs with index 1 and index 5. 9 == 3 * 3 gives (2, 3). The 4 at index 4 pairs only with the -2 at index 5, because the 2 at index 1 comes before it.
Example 2
nums = [1,1,1]return = 31 == 1 * 1, so every pair of indices is valid: (0, 1), (0, 2) and (1, 2).
Example 3
nums = [2,4,-1,1]return = 04 == 2 * 2, but 4 is at index 1, after the 2 at index 0. The square has to come first, so this pair does not count.
1 == (-1) * (-1), but again 1 comes after -1. No square of a number is negative, so -1 can never be the earlier number. There are no valid pairs.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
More AuxoAI Online Assessment questions
Similar questions at other companies
- Basic Item DiscountsPalantir · OAPalantir interview questions
- Distinct Products After Removing One ElementHSBC · OAHSBC interview questions
- Find Max Sum with Same First and Last DigitMicrosoft · OAMicrosoft interview questions
- Stock PricesRubrik · OARubrik interview questions
- Get Max Discount PairsAmazon · OA
- Find Number of Interesting PairsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
- Nums That Are Divisible by N 🍋Two Sigma · OATwo Sigma interview questions
- Find Mean and ModeCisco · OACisco interview questions
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Get Triplet CountIBM · OAIBM interview questions