FastPrepFind the Value Occurring Exactly Once

Find the Value Occurring Exactly Once

Morgan Stanley logoMorgan Stanley● MediumFULLTIMEONSITE INTERVIEW

Updated

Problem statement

Given an integer array nums, return the value that occurs exactly once. Exactly one distinct value has frequency one. Every other distinct value occurs at least twice, with no restriction on whether its frequency is odd or even.

For this exercise, inspect the input array in one left-to-right pass and leave it unchanged. You may store frequency counts and inspect those stored records after the array pass. Return the value rather than its index. No parity assumption is made.

Function

singleOccurrence(nums: int[]) → int

Examples

Example 1

nums = [1,2,3,2,3,3,3,3,3,3,3,3,4,4,4,5,5]return = 1

The frequencies are 1:1, 2:2, 3:9, 4:3, and 5:2. Only value 1 appears once. Raw XOR of the array is 6, demonstrating why an unreported even-frequency promise cannot be assumed.

Example 2

nums = [6,6,6,6,0,9,9,9]return = 0

Zero occurs once, 6 occurs four times, and 9 occurs three times. The answer is 0. An odd frequency such as three does not make a value eligible.

Constraints

  • For this exercise, assume 1 <= nums.length <= 5000.
  • For this exercise, assume 0 <= nums[i] <= 1000000.
  • Exactly one distinct value occurs once; every other distinct value occurs at least twice.

More Morgan Stanley Onsite Interview questions

Similar questions at other companies

Interview reports that mention this question

Morgan Stanley interview experiences

All Morgan Stanley interview questionsSee Morgan Stanley hiring insights
Saved
class Solution {
    public int singleOccurrence(int[] nums) {
        // Read nums once from left to right.
    }

}
Checking account…