Count Valid Bitwise Pairs
Updated
Problem statement
Stripe's analytics team is studying relationships between values stored in an array.
Given an array A of N non-negative integers and a non-negative integer K, determine the number of index pairs (i, j) such that 1 <= i < j <= N and:
3(A_i | A_j) - (A_i & A_j) - A_i - A_j + (A_i XOR A_j)^2 - ((A_i | A_j) - (A_i & A_j))^2 + (A_i XOR A_j) + (A_i & A_j) + (A_i | A_j) = K + A_j + 2(A_i XOR A_j)Here |, &, and XOR denote bitwise OR, AND, and XOR. Return the total number of valid pairs.
Equivalent condition
Using the standard bitwise identities A_i | A_j = (A_i & A_j) + (A_i XOR A_j) and A_i + A_j = (A_i | A_j) + (A_i & A_j), the equation simplifies to:
A_i + (A_i XOR A_j) = K
The order remains important: A_i is the earlier value because i < j.
Batch input and output format
The batch input has T test cases. Each test case contains N, K, and the array A, and outputs one count. The function below handles one test case.
Function
countValidBitwisePairs(A: long[], K: long) → longExamples
Example 1
A = [1,2,3]K = 4return = 1The pair at 1-based indices (1, 2) is valid because 1 + (1 XOR 2) = 4. The other two pairs produce 3.
Example 2
A = [0,15]K = 15return = 1The only pair is valid: 0 + (0 XOR 15) = 15.
Example 3
A = [15,0]K = 15return = 0The condition is asymmetric. Here 15 + (15 XOR 0) = 30, so reversing the values from Example 2 changes the answer to zero.
Constraints
- For one test case,
1 <= A.length <= 10^5. 0 <= K <= 10^18.0 <= A[i] <= 10^18.- In the batch format,
1 <= T <= 200and the sum ofNover all test cases does not exceed3 * 10^5.
More Stripe Online Assessment questions
- Financial Account LedgerOA · PHONE SCREEN · Seen Nov 2026
- Chat Billing CalculationOA · Seen Nov 2026
- Deployment Window SchedulerOA · Seen Nov 2026
- Asynchronous Event ProcessingOA · Seen Nov 2026
- Subscription and Usage-Based Billing CalculatorOA · Seen Nov 2026
- Split Tender Part 4 - RefundsOA · PHONE SCREEN · Seen Nov 2026
- Request Routing SystemOA · Seen Nov 2026
- Incident MonitorOA · Seen Nov 2026
- Split Tender Part 3 - SurchargesOA · Seen Nov 2026
- Split Tender Part 2 - Expiration DatesOA · Seen Nov 2026
Similar questions at other companies
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Bitwise XOR SubsequencesJP Morgan Chase · OAJP Morgan Chase interview questions
- Bitwise XOR SubsequencesGoldman Sachs · OAGoldman Sachs interview questions
- Count Subarrays With Given XORInMobi · OAInMobi interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Palindrome-Rearrangeable PairsExpedia · OAExpedia interview questions
- Find the Unpaired NumbersAdobe · PHONE SCREENAdobe interview questions
- Wildcard Address-Book QueriesGoogle · PHONE SCREENGoogle interview questions
- Find the Unique Element Among PairsChubb · PHONE SCREENChubb interview questions
- Count Overlapping Square PairsRamp · OARamp interview questions
Stripe interview experiences
- Stripe SWE Onsite over Two Days: 1 Experience
- Stripe New Grad SWE Phone Screen and Onsite: 2 Experiences
- Stripe AI Coding Interview, Experienced SWE: 6 Experiences
- Stripe SWE Intern Payout Scheduler Phone Screen: 1 Experience
- Stripe New Grad SWE Onsite and HM Round: 1 Experience
- Stripe Experienced MLE Phone Screens: 1 Experience