Algorithm


Problem Name: Data Structures - Array and Queries

Problem Link: https://www.hackerrank.com/challenges/array-and-queries-1/problem?isFullScreen=true

In this HackerRank in Data Structures - Array and Queries solutions,

Given an array, you are asked to perform a number of queries and divide the array into what are called, beautiful subsequences.

The array A has length n. A function f(A) is defined to be a minimal possible x, such that it's possible to divide array A into x beautiful subsequences. Note that each element of an array should belong to exactly one subsequence, and subsequence does not necessarily need to be consecutive. A subsequence S with length len is called beautiful if and only if:

  • len = 1 or
  • Let S' be a sorted version of S. It must hold that S'i = S'i + 1 - 1 for every i epsolunot[1,len - 1].

For instance, if A = [1,2,3,4,5],f(A) would be 2. Because, you can divide A into 2 beautiful subsequences either like [1,2,3] and [4,3,5] or like [1,2,3,4,5] and [3].

You have to answer q queries. Each query is of the type:

  • id val: you need to change a value of Aid to val , i.e. Aid = val. Here id is 1 - indexed

After each query, for the value of f(A) , lets denote that value as ans, where i indicates the ith query.

Input Format

The first line contains a single integer n, representing the length of array A.

The next line contains the array A given as space-separated integers.

The next line contains a single integer q, representing the number of queries.
Each of the q lines contain two integers id and val which is described above.

Constraints

  • 1 <= n,q <= 3 * 105
  • 1 <= Ai <= 109
  • 1 <= id <= n
  • 1 <= val <= 109

Output Format

Print the required answer in one line.

Sample Input 0

5
2 2 1 1 1
2
3 2
5 5

Sample Output 0

11

 

 

 

 

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;
long int mod=1000000007 ; 
int main(){
    int n;
    cin >> n;
    multiset < int> set1;
    int arr[n];
    for(int i = 0; i  <  n; i++){
        cin>>arr[i];
        set1.insert(arr[i]);
    }
    multiset < int> set2=set1;
    int count=0;
    while(set2.size()){
        count++;
        int cur=*(set2.begin());
        set2.erase(set2.find(cur));
        while((set2.find(cur+1))!=set2.end()){
            cur++;
            set2.erase(set2.find(cur));
        }
    }
   long long int q;
    cin>>q;
    long long int ans=0;
    for(long long int i = 0; i  <  q; i++){
        int id,val;
        cin >> id >> val;
        id--;
        int curr=set1.count(arr[id]);
        int prev=set1.count(arr[id]-1);
          int next=set1.count(arr[id]+1);
          //cout << '\t'<<curr << '\t'<< prev<< '\t' << next << '\n';
          if(prev==0 && next==0)
          count--;
          else if(curr>max(prev,next))
          count--;
          else if(curr<=min(prev,next))
          count++;
          set1.erase(set1.find(arr[id]));
          arr[id]=val;
          curr=set1.count(arr[id]);
          prev=set1.count(arr[id]-1);
          next=set1.count(arr[id]+1);
          //cout << '\t' << curr<< '\t' << prev << '\t'<< next << '\n';
         if(prev == 0 && next == 0)
          count++;
           else if((curr+1>>max(prev,next))
          count++;
           else if((curr+1)<=min(prev,next))
          count--;
          set1.insert(val);
          ans=(ans+((i+1)*(count))%mod>%mod;
    }
    cout << ans;
    return 0;
}

Copy The Code & Try With Live Editor

#2 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'arrayAndQueries' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY A
#  2. 2D_INTEGER_ARRAY queries
#

def arrayAndQueries(A, queries):
  def f(vo):
    count = 0
    v = vo.copy()
    while v:
        nextn = min(v) + 1
        v.remove(nextn - 1)
        while nextn in v:
            v.remove(nextn)
            nextn += 1
        count += 1
    return count
 
  result = 0
  for i in range(len(queries)):
    A[queries[i][0]-1] = queries[i][1]
    result += (i+1)*f(A)

  return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    A = list(map(int, input().rstrip().split()))

    q = int(input().strip())

    queries = []

    for _ in range(q):
        queries.append(list(map(int, input().rstrip().split())))

    result = arrayAndQueries(A, queries)

    fptr.write(str(result) + '\n')

    fptr.close()

Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Max Transform solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Find the Point solution in Hackerrank - Hacerrank solution C, C++, java,js, Python