// For two arrays of integers of length N, // for all K from 1 to N, count the number of common numbers in prefixes of length K. // The numbers within the arrays may repeat, and the intersection is counted without considering multiplicity. // A prefix of length K of array A is the first K elements of array A // A [1, 1] => [1], [1, 1] // B [1, 1] => [1], [1, 1] // R [1, 1] // [1, 2, 5] => [1], [1, 2], [1, 2, 5] // [1, 5, 4] => [1], [1, 5], [1, 5, 4] // [1, 1, 2]

Task: For each K from 1 to N, count the number of common unique numbers in the prefixes of length K of two arrays.

Solution idea:

• Use two sets to store unique elements of each prefix.
• Iterate over indices from 0 to N-1, adding elements to the respective sets.
• At each step, count the intersection of the sets and record the size of the intersection.

Example in Go:

package main

import (
	"fmt"
)

func commonPrefixCounts(A, B []int) []int {
	N := len(A)
	setA := make(map[int]struct{})
	setB := make(map[int]struct{})
	result := make([]int, N)

	for i := 0; i < N; i++ {
		setA[A[i]] = struct{}{}
		setB[B[i]] = struct{}{}

		count := 0
		for val := range setA {
			if _, exists := setB[val]; exists {
				count++
			}
		}
		result[i] = count
	}
	return result
}

func main() {
	A := []int{1, 2, 5}
	B := []int{1, 5, 4}
	res := commonPrefixCounts(A, B)
	fmt.Println(res) // Output: [1 2 2]
}

This approach works in O(N*M), where M is the average number of unique elements in the prefixes. For optimization, data structures with frequency counting and dynamic intersection updates can be used.