Bit Manipulation Under Constraints

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Bit Manipulation Under Constraints. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Yelp's review-quality pipeline encodes each processed review batch as an integer fingerprint. Due to duplicated processing, every fingerprint appears exactly three times except one fingerprint that appears once. Given the list of fingerprints, return the unique value using bit manipulation.

You must run in linear time and use constant extra space. Input values are signed 32-bit integers, and the returned value must also be interpreted as a signed 32-bit integer.

Formal Specification

Implement single_number(nums), where nums is a non-empty list of integers. Exactly one value appears once, and every other distinct value appears exactly three times. Return the value that appears once.

Constraints

1 <= len(nums) <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
Exactly one value appears once
Every other distinct value appears exactly three times

Function Signature

def single_number(nums):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output