Multiplexer
Source: codechef
Difficulty: 1961

Multiplexer
You are given an array$A$of length$N$and a positive integer$X$. You are allowed to perform the following operation
at most once
:
Choose any contiguous subarray of$A$and multiply each element of the subarray by$X$.
Your task is to determine the maximum possible frequency of any element in the array after performing the operation at most once. The frequency of an element is defined as the number of times it appears in the array.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers$N$and$X$— the length of array and the multiplier, respectively.
The next line contains$N$space-separated integers$A_1, A_2, ..., A_{N}$— the elements of the array.
Output Format
For each test case, output a single line containing one integer — the maximum frequency of any element that can be achieved after performing the operation at most once.
Constraints$1 \leq T \leq 10^4$$1 \leq N \leq 2\cdot10^{5}$$1 \leq X, A_i \leq 10^{9}$The sum of$N$over all test cases won't exceed$2\cdot10^{5}$.
Sample 1:
Explanation:
Test Case 1:
Multiplying any subarray by$X=1$leaves the array unchanged. Therefore, no operation is needed, and the maximum frequency remains$1$.
Test Case 2:$[10, 2, 8, 2, 4] \xrightarrow{\text{Choose Substring from }l=2 \text{ to } r=5} [10, 10, 40, 10, 20]$. It can be shown that there is no way to achieve a maximum frequency greater than$3$.
Test Case 3:$[6, 2, 6, 2] \xrightarrow{\text{Choose Substring from }l=2 \text{ to } r=4} [6, 6, 18, 6]$. It can be shown that there is no way to achieve a maximum frequency greater than$3$.
Test Case 4:$[5, 3, 2, 5, 4] \xrightarrow{\text{Choose Substring from }l=3 \text{ to } r=3} [5, 3, 4, 5, 4]$.
The frequency of both$5$and$4$is$2$, and it can be shown that no operation can yield a maximum frequency greater than$2$

Sample Input:
4
2 1
1 6
5 5
10 2 8 2 4
4 3
6 2 6 2
5 2
5 3 2 5 4

Sample Output:
1
3
3
2

C++ solution:
#include <bits/stdc++.h>
using namespace std;

int solve() {
  int N, X;
  cin >> N >> X;
  // प्रत्येक संख्या के सभी स्थान (इंडेक्स) को स्टोर करने के लिए मैप
  unordered_map<int, vector<int>> occ;
  for (int x, i = 0; i < N; ++i) {
    cin >> x;
    occ[x].push_back(i); // संख्या x के इंडेक्स को स्टोर करें
  }

  int ans = 1; // न्यूनतम आवृत्ति 1 है (कम से कम एक तो होगा)

  // प्रत्येक संख्या (target) के लिए प्रोसेस करें
  for (auto &[target, idxs] : occ) {
    int m = idxs.size(); // target की मूल आवृत्ति
    ans = max(ans, m);   // मूल आवृत्ति को अपडेट करें

    // X=1 होने पर कुछ नहीं करना (गुणा करने से कोई बदलाव नहीं)
    if (X == 1) continue;

    // यदि target, X से विभाज्य नहीं है, तो skip करें
    if (target % X != 0) continue;

    // k = target / X (जिसे X से गुणा करने पर target मिलेगा)
    int k = target / X;
    auto it = occ.find(k);
    vector<int> k_idxs;

    // यदि k मौजूद है, तो उसके इंडेक्स लें
    if (it != occ.end()) {
      k_idxs = it->second;
    }

    int p = k_idxs.size(); // k की मूल आवृत्ति
    int min_psum = 0;      // न्यूनतम प्रीफिक्स योग
    int cur_psum = 0;      // वर्तमान प्रीफिक्स योग
    int i = 0, j = 0;      // दो पॉइंटर्स (k और target के इंडेक्स के लिए)

    // दो पॉइंटर्स का उपयोग करके सबसे अच्छा सबअरे खोजें
    while (i < m || j < p) {
      // दोनों सूचियों से अगला इंडेक्स चुनें
      int a = (i < m) ? idxs[i] : INT_MAX;
      int b = (j < p) ? k_idxs[j] : INT_MAX;

      bool advance_i = a < b; // किस सूची को आगे बढ़ाना है?
      int value = advance_i ? -1 : 1; // प्रीफिक्स योग में परिवर्तन

      cur_psum += value;
      // उपलब्ध अधिकतम आवृत्ति की गणना (current - min_prefix + m)
      ans = max(ans, cur_psum - min_psum + m);
      min_psum = min(min_psum, cur_psum);

      // चुनी गई सूची को आगे बढ़ाएँ
      if (advance_i) ++i;
      else ++j;
    }
  }
  return ans;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--)
    cout << solve() << '\n';
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

type Pair struct {
    Idx, Val int
}

func main() {
    in := bufio.NewReader(os.Stdin)
    line, _ := in.ReadString('\n')
    T, _ := strconv.Atoi(strings.TrimSpace(line))
    for t := 0; t < T; t++ {
        line, _ = in.ReadString('\n')
        parts := strings.Fields(line)
        N, _ := strconv.Atoi(parts[0])
        X, _ := strconv.ParseInt(parts[1], 10, 64)
        A := make([]int64, N)
        line, _ = in.ReadString('\n')
        parts = strings.Fields(line)
        for i := 0; i < N; i++ {
            A[i], _ = strconv.ParseInt(parts[i], 10, 64)
        }
        freq := make(map[int64]int, N*2)
        pos := make(map[int64][]int, N*2)
        for i := 0; i < N; i++ {
            freq[A[i]]++
            pos[A[i]] = append(pos[A[i]], i)
        }
        ans := 0
        for _, v := range freq {
            if v > ans {
                ans = v
            }
        }
        if X == 1 {
            fmt.Println(ans)
            continue
        }
        for v, idxs := range pos {
            Y := v * X
            origY := 0
            if val, ok := freq[Y]; ok {
                origY = val
            }
            merged := make([]Pair, 0, len(idxs)+len(pos[Y]))
            for _, idx := range idxs {
                merged = append(merged, Pair{idx, 1})
            }
            if arr, ok := pos[Y]; ok {
                for _, idx := range arr {
                    merged = append(merged, Pair{idx, -1})
                }
            }
            sort.Slice(merged, func(i, j int) bool { return merged[i].Idx < merged[j].Idx })
            bestSum, curSum := -1<<31, 0
            for _, p := range merged {
                if p.Val > curSum+p.Val {
                    curSum = p.Val
                } else {
                    curSum += p.Val
                }
                if curSum > bestSum {
                    bestSum = curSum
                }
            }
            if bestSum < 0 {
                bestSum = 0
            }
            if origY+bestSum > ans {
                ans = origY + bestSum
            }
        }
        fmt.Println(ans)
    }
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() throws IOException {
            byte[] buf = new byte[1024]; // Initial buffer size
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') // Stop at newline
                    break;
                if (cnt == buf.length) // Resize buffer if needed
                    buf = Arrays.copyOf(buf, buf.length * 2);
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public String next() throws IOException {
            byte[] buf = new byte[64]; // initial buffer size
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == ' ' || c == '\n') // Stop at space or newline
                    break;
                if (cnt == buf.length) // Resize buffer if needed
                    buf = Arrays.copyOf(buf, buf.length * 2);
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') // Skip whitespace
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return neg ? -ret : ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') // Skip whitespace
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return neg ? -ret : ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') // Skip whitespace
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') // Handle fractional part
                while ((c = read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);
            return neg ? -ret : ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

    static Reader s = new Reader();
    static PrintWriter p = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static int mod = 1_000_000_007;
    static int imax = Integer.MAX_VALUE;
    static int imin = Integer.MIN_VALUE;
    static long lmax = Long.MAX_VALUE;
    static long lmin = Long.MIN_VALUE;

    private static void solve() throws IOException {

        var n = s.nextInt();
        var x = s.nextLong();

        var nums = new long[n];
        var mpo = new HashMap<Long, Integer>();
        var mpa = new HashMap<Long, int[]>();

        for (int i = 0; i < n; ++i) {
            nums[i] = s.nextLong();
        }

        for (var num : nums) {
            mpo.put(num, mpo.getOrDefault(num, 0) + 1);
        }

        for (var key : mpo.keySet()) {
            var arr = mpa.getOrDefault(key, new int[3]);
            var multipleFreq = mpo.getOrDefault(key * x, 0);
            arr[2] = arr[1] = arr[0] = multipleFreq;
            mpa.put(key, arr);
        }

        var max = 0;

        for (var num : mpo.keySet()) {
            max = Math.max(max, mpo.get(num));
        }

        if (x == 1) {
            p.println(max);
            return;
        }

        for (var num : nums) {

            var arr = mpa.get(num);

            arr[0]++;
            arr[1] = Math.max(arr[1], arr[0]);

            if (num % x == 0 && mpo.containsKey(num / x)) {
                var arr2 = mpa.get(num / x);
                arr2[0] -= 1;
                arr2[1] = Math.max(arr2[1], arr2[0]);
                arr2[0] = Math.max(arr2[0], arr2[2]);
                mpa.put(num / x, arr2);
            }
        }

        for (var num : mpa.keySet()) {
            max = Math.max(max, mpa.get(num)[1]);
        }

        p.println(max);

    }

    public static void main(String args[]) throws IOException {

        int t = s.nextInt();

        while (--t >= 0) {
            solve();
            p.flush();
        }

    }
}

JavaScript solution:
process.stdin.resume();
process.stdin.setEncoding("utf-8");

let inputData = "";
process.stdin.on("data", (chunk) => {
    inputData += chunk;
});

process.stdin.on("end", () => {
    let inputLines = inputData.trim().split("\n");
    let index = 0;
    let testCases = parseInt(inputLines[index++], 10);

    while (testCases--) {
        let [n, factor] = inputLines[index++].split(" ").map(Number);
        let arr = inputLines[index++].split(" ").map(Number);

        let frequency = new Map();
        let indices = new Map();

        for (let i = 0; i < n; i++) {
            let value = arr[i];
            if (!frequency.has(value)) {
                frequency.set(value, 0);
                indices.set(value, []);
            }
            frequency.set(value, frequency.get(value) + 1);
            indices.get(value).push(i);
        }

        let maxCount = 0;
        for (let count of frequency.values()) {
            maxCount = Math.max(maxCount, count);
        }

        if (factor === 1) {
            console.log(maxCount);
            continue;
        }

        for (let [value, indexList] of indices.entries()) {
            let target = value * factor;
            if (!indices.has(target)) continue;

            let originalCount = frequency.get(target) || 0;
            let combined = [];
            
            for (let idx of indexList) combined.push([idx, 1]);
            for (let idx of indices.get(target)) combined.push([idx, -1]);

            combined.sort((a, b) => a[0] - b[0]);

            let bestSegment = 0, currentSum = 0;
            for (let [, val] of combined) {
                currentSum = Math.max(val, currentSum + val);
                bestSegment = Math.max(bestSegment, currentSum);
            }

            maxCount = Math.max(maxCount, originalCount + bestSegment);
        }

        console.log(maxCount);
    }
});

Python solution:
# cook your dish here
for i in range(int(input())):
    def calc(a):
        ans = cur = 0
        for x in a:
            cur = max(0, cur + x)
            ans = max(ans, cur)
        return ans
    N,X=map(int,input().split())
    A=list(map(int,input().split()))
    D={}
    ans=0
    for i in range(len(A)):
        if A[i] not in D:
            D[A[i]]=[]
        D[A[i]].append(i)
    for i in D.keys():
        a=i
        b=X
        ans=max(ans,len(D[a]))
        if D.get(b*a,0)==0 or X==1:
            continue
        else:
            p=0
            q=0
            B=[]
            while p<len(D[a]) or q<len(D[a*b]):
                if p==len(D[a]):
                    B.append(-1)
                    q+=1
                elif q==len(D[a*b]):
                    B.append(1)
                    p+=1
                elif D[a][p]<D[a*b][q]:
                    B.append(1)
                    p+=1
                else:
                    B.append(-1)
                    q+=1
            ans=max(ans,calc(B)+len(D[a*b]))
    print(ans)

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  t = input[ptr].to_i
  ptr += 1
  t.times do
    n, x = input[ptr].to_i, input[ptr + 1].to_i
    ptr += 2
    a = input[ptr, n].map(&:to_i)
    ptr += n

    freq = Hash.new { |h, k| h[k] = [] }
    a.each_with_index do |num, idx|
      freq[num] << idx
    end

    max_freq = freq.values.map(&:size).max || 0

    freq.each_key do |num|
      target = num * x
      next if x == 1 || !freq.key?(target)

      list_num = freq[num]
      list_target = freq[target]

      p = 0
      q = 0
      b = []
      while p < list_num.size || q < list_target.size
        if p == list_num.size
          b << -1
          q += 1
        elsif q == list_target.size
          b << 1
          p += 1
        elsif list_num[p] < list_target[q]
          b << 1
          p += 1
        else
          b << -1
          q += 1
        end
      end

      current = 0
      best = 0
      b.each do |val|
        current = [current + val, 0].max
        best = [best, current].max
      end

      total = best + list_target.size
      max_freq = [max_freq, total].max
    end

    puts max_freq
  end
end

solve