1354. Construct Target Array With Multiple Sums

using System;
using System.Collections.Generic;
public class Solution {
    public bool IsPossible(int[] target) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        long total = 0;
        foreach (var num in target) {
            total += num;
            pq.Enqueue(num, num);
        }
        
        while (pq.Peek() > 1) {
            int maxVal = pq.Dequeue();
            total -= maxVal;
            if (maxVal < total || total == 0 || maxVal % total == 0) return false;
            pq.Enqueue(maxVal % total, maxVal % total);
            total += pq.Peek();
        }
        return true;
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsPossible(vector<int>& target) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        long total = 0;
        foreach (var num in target) {
            total += num;
            pq.Enqueue(num, num);
        }
        
        while (pq.Peek() > 1) {
            int maxVal = pq.Dequeue();
            total -= maxVal;
            if (maxVal < total || total == 0 || maxVal % total == 0) return false;
            pq.Enqueue(maxVal % total, maxVal % total);
            total += pq.Peek();
        }
        return true;
    }
}

import java.util.PriorityQueue;

public class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        long total = 0;
        for (int num : target) {
            total += num;
            pq.add(num);
        }
        
        while (pq.peek() > 1) {
            int maxVal = pq.poll();
            total -= maxVal;
            if (maxVal < total || total == 0 || maxVal % total == 0) return false;
            pq.add(maxVal % total);
            total += pq.peek();
        }
        return true;
    }
}

var isPossible = function(target) {
    let pq = new MaxPriorityQueue({ priority: x => x });
    let total = target.reduce((acc, num) => acc + num, 0);
    target.forEach(num => pq.enqueue(num));
    
    while (pq.front().element > 1) {
        let maxVal = pq.dequeue().element;
        total -= maxVal;
        if (maxVal < total || total === 0 || maxVal % total === 0) return false;
        pq.enqueue(maxVal % total);
        total += pq.front().element;
    }
    return true;
};

import heapq

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        total = sum(target)
        target = [-x for x in target]
        heapq.heapify(target)
        
        while -target[0] > 1:
            maxVal = -heapq.heappop(target)
            total -= maxVal
            if maxVal < total or total == 0 or maxVal % total == 0:
                return False
            maxVal %= total
            total += maxVal
            heapq.heappush(target, -maxVal)
        return True

import (
    "container/heap"
)

func isPossible(target []int) bool {
    pq := &MaxHeap{}
    heap.Init(pq)
    total := 0
    for _, num := range target {
        heap.Push(pq, num)
        total += num
    }
    
    for (*pq)[0] > 1 {
        maxVal := heap.Pop(pq).(int)
        total -= maxVal
        if maxVal < total || total == 0 || maxVal % total == 0 {
            return false
        }
        heap.Push(pq, maxVal % total)
        total += (*pq)[0]
    }
    return true
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Algorithm

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:

Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.

Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:

Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.

Проверить несколько условий:

Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.

Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.

Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:

Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎