DDSA Solutions

3289. The Two Sneaky Numbers of Digitville

MediumView on LeetCode
ArrayHash TableMath
Time: O(n)
Space: O(n)

Problem Overview

Count subarrays where product is divisible by a prime p.

Intuition

Count subarrays where product is divisible by a prime p. Use sliding window or prefix products.

Algorithm

  1. 1Count subarrays where at least one element is divisible by p.
  2. 2Total subarrays - subarrays with no element divisible by p.

Common Pitfalls

  • •Subarrays with no multiple of p: find runs with no multiple of p, count subarrays in each run.
3289.cs
C#
// Approach: Find duplicate by tracking seen values; repeated and missing follow from XOR or count.
// Time: O(n) Space: O(n)

public class Solution
{
    public int[] GetSneakyNumbers(int[] nums)
    {
        // Array to store the result (two duplicate numbers)
        int[] result = new int[2];

        // Frequency counter array (assuming numbers range from 0 to 99)
        int[] frequencyCounter = new int[100];

        // Index to track position in result array
        int resultIndex = 0;

        // Iterate through each number in the input array
        foreach (int currentNumber in nums)
        {
            // Increment the frequency count for current number
            frequencyCounter[currentNumber]++;

            // If this number appears for the second time, add it to result
            if (frequencyCounter[currentNumber] == 2)
            {
                result[resultIndex] = currentNumber;
                resultIndex++;
            }
        }

        return result;
    }
}
Was this solution helpful?

Related Problems