Fascinating Multiple Number

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-1 times) :

  • 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*3 value 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-1 times according to the algorithms for beginners, where N is the size of our array.

Method 2 :

  • We need to geneate a max-heap from the elements of array of size N to 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-1 times.
  • 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() :

  1. Insert the item at the last index, and increment the size by 1.
  2. Then, check if the inserted item is smaller than its parent,
  3. If yes, then swap the inserted item with its parent.
  4. If no, then do nothing.
  5. Now, go to step 2 and repeat untill we reach root (first element).

Extract() :

  1. Store the value of the first node of our heap ( temp = heap[0] ).
  2. Replace the root node with the farthest right node (last element).
  3. Decrease the size by 1. (heap[0] = heap[size-1])
  4. Perform heapify starting from the new root.
  5. Return the stored value.(temp)

Heapify () :

  1. if the heap property holds true then you are done.
  2. else if
  3. replacement node value > its parent nodes value
    then swap them, and repeat step 3.
  4. else
  5. 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;
    }
}
Previous post Swap Sum
Next post Small Group

Leave a Reply

Your email address will not be published. Required fields are marked *