Last Updated on March 28, 2022 by Ria Pathak
Concepts Used
Heap
Difficulty Level
Medium
Problem Statement :
Given an array A of size
N, we have to perform following operations, untill only one integer remains (N-1times) :
- Select two elements P and Q from the array A where P is the maximum and Q is the second maximum element.
- Delete the chosen elements from the array.
- Insert
((P∗3)−(Q∗2))%(109+7) in the array.
See original problem statement here
Solution Approach :
Introduction :
To get the first two maximum numbers we can create max-heap of the elements of the array and extract two elements (maximum & second maximum), perform the operations, then insert the new value to the max-heap.
Note – Check for integer overflows, for example consider this array 10000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1, in this our
p*3value will overflow while calculating so for safeguarding we will apply modulo in each subcalculation as well,((P∗3)%(109+7)−(Q∗2)%(109+7)).
Method 1 :
In order to get highest and second highest values every time we can get highest and second highest values in a single traversal. After extracting both the values , perform the operation and add it back to the array, now again find highest and the second highest values. Repeat the process
N-1times, whereNis the size of our array.
Method 2 :
- We need to geneate a max-heap from the elements of array of size
Nto get the maximum elements.- In a max-heap, the root always stores the larger value as compared to its left & right subtree, this condition needs to be true for every node. We need to insert each item one by one such that parent is always larger than the item itself. If parent is smaller, then swap the current item with its parent.
- After generating max-heap now extract the first two elements and perform the operation, then add the new obtained value back to the heap using insert().
- Repeat the above process
N-1times.- Print the element, this is our required answer.
extract(): Removes the maximum element from Max-Heap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.
heapify(): Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case of max-heap), than the node.
Below is the algorithm of above approach.
Algorithms :
Insert() :
- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
2and repeat untill we reach root (first element).
Extract() :
- Store the value of the first node of our heap (
temp = heap[0]).- Replace the root node with the farthest right node (last element).
- Decrease the size by
1.(heap[0] = heap[size-1])- Perform heapify starting from the new root.
- Return the stored value.(temp)
Heapify ():
- if the heap property holds true then you are done.
- else if
- replacement node value > its parent nodes value
then swap them, and repeat step 3.- else
- swap the replacement node with the largest child node, and
repeat step 3.
Example:
Solutions:
#include <stdio.h>
#define mod 1000000007
#define ll long long int
int parent(int i)
{
return (i-1)/2;
}
int left(int i)
{
return (i*2)+1;
}
int right(int i)
{
return (i*2)+2;
}
void swap(ll *a,ll *b)
{
ll temp = *a;
*a = *b;
*b = temp;
}
void insert(ll heap[],int *size, ll val)
{
heap[*size] = val;
int i = *size;
(*size)++;
while(i!=0 && heap[parent(i)]<heap[i])
{
swap(&heap[parent(i)],&heap[i]);
i = parent(i);
}
}
void heapify(ll heap[],int i,int size)
{
int l = left(i);
int r = right(i);
int s = i;
if(l<size && heap[l]>heap[i])
s = l;
if(r<size && heap[r]>heap[s])
s = r;
if(s!=i)
{
swap(&heap[i],&heap[s]);
heapify(heap,s,size);
}
}
ll extract(ll heap[],int *size)
{
ll root = heap[0];
heap[0] = heap[(*size)-1];
(*size)--;
heapify(heap,0,*size);
return root;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
ll *heap =(ll *)malloc(sizeof(ll)*n);
int size=0;
for(int i=0;i<n;i++)
{
ll t;
scanf("%lld",&t);
insert(heap,&size,t);
}
while(--n)
{
ll p = extract(heap,&size);
ll q = extract(heap,&size);
ll ans = ((p*3)%mod - (q*2)%mod)%mod;
insert(heap,&size,ans);
}
printf("%lld\n",heap[0]);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int parent(int i)
{
return (i-1)/2;
}
int left(int i)
{
return (i*2)+1;
}
int right(int i)
{
return (i*2)+2;
}
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void insert(int heap[],int *size, int val)
{
heap[*size]= val;
int i = *size;
(*size)++;
while(i!=0 && heap[parent(i)]>heap[i])
{
swap(&heap[parent(i)],&heap[i]);
i = parent(i);
}
}
void heapify(int heap[],int i,int size)
{
int l = left(i);
int r = right(i);
int lar = i;
if(lar<size && heap[l]<heap[i])
lar = l;
if(r<size && heap[r]<heap[lar])
lar = r;
if(lar!=i)
{
swap(&heap[i],&heap[lar]);
heapify(heap,lar,size);
}
}
int extract(int heap[],int *size)
{
int root = heap[0];
heap[0] = heap[*size-1];
(*size)--;
heapify(heap,0,*size);
return root;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int *heap = (int *)malloc(sizeof(int)*n);
int size = 0;
for(int i=0;i<n;i++)
{
int t;
cin>>t;
insert(heap,&size,t);
}
while(size>1)
{
ll p = extract(heap,&size);
ll q = extract(heap,&size);
ll ans = ((p*3)%mod - (q*2)%mod)%mod;
insert(heap,&size,ans);
}
cout<<heap[0]<<endl;
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int mod=1000000007;
while(t-->0){
int size=sc.nextInt();
long[] arr=new long[size+1];
arr[0]=Integer.MIN_VALUE;
for(int i=1;i<=size;i++){
int temp=sc.nextInt();
insert(arr,i,temp);
}
build(arr,size);
while(size>1){
if(size==2){
long P=arr[1];
long Q=arr[2];
long opt=(P*3-Q*2)%mod;
arr[1]=opt;
size--;
}
else{
long P=extract(arr,size--);
long Q=extract(arr,size--);
long opt=(P*3-Q*2)%mod;
insert(arr,++size,opt);
//build(arr,size);
}
}
System.out.println(arr[1]);
}
}
static void max_heap(long[] arr, int i,int size){
if(isLeaf(i,size)) return;
int right=i*2+1;
int left=i*2;
if(right<=size){
if(arr[i]>=arr[right]&&arr[i]>=arr[left]) return;
}
else{
if(left<=size&&arr[i]>=arr[left]) return;
}
int largest=i;
if(left<=size&&arr[largest]<arr[left]) largest=left;
if(right<=size&&arr[largest]<arr[right]) largest=right;
if(largest!=i) swap(arr,largest,i);
max_heap(arr,largest,size);
}
static boolean isLeaf(int i,int size){
if(i>size/2&&i<=size) return true;
else return false;
}
static void swap(long[] arr,int i, int j){
long temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
static void insert(long[] arr, int i,long value){
arr[i]=value;
int k=i;
while(k>1&&arr[k]>arr[k/2]){
swap(arr,k,k/2);
k=k/2;
}
}
static void build(long[] arr, int size){
int non_leaf=size/2;
for(int i=non_leaf;i>0;i--) max_heap(arr,i,size);
}
static long extract(long[] arr,int size){
long temp=arr[1];
swap(arr,1,size);
max_heap(arr,1,size-1);
return temp;
}
}
[forminator_quiz id="1719"]
This article tried to discuss Heap. Hope this blog helps you understand and solve the problem. To practice more problems on Heap you can check out MYCODE | Competitive Programming.