1354. Construct Target Array With Multiple Sums

leetcode hard

#array#backtracking#csharp#hard#heap#leetcode#math#queue

Task

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.

Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.

Вы можете повторять эту процедуру столько раз, сколько потребуется.

Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример

Input: target = [8,5]

Output: true

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#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;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

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;
};

Python solution

matched/original

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

Go solution

matched/original

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
}

Explanation

Algorithm

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

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

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

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

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

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

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

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

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

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

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

😎