Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/array-and-queries-1/problem?isFullScreen=true
In this HackerRank in Data Structures -
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 ansi , 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;
}
#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()