We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Array and Queries
  5. Discussions

Array and Queries

Sort by

recency

|

7 Discussions

|

  • lamphanviet
     + 0 comments

    Time Limit of this problem needs to be adjusted for Java.

    Just by simply reading all the inputs, and let's say putting all the values into a HashMap and simply return 0 (no other calculation done), you already got TLE for ~10 test cases.

  • adsalunke090
     + 2 comments

    **for more info on problem visit below link https://www.hackerrank.com/contests/hackerrank-hiring-contest/challenges/array-and-queries-1/problem

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

  • moisesmarques
     + 0 comments

    I don't know how to solve yet, but, something I know is that the query modify just one element in the list. So maybe you should recalculate a partition of that list instead the entire list.

  • manas_rishav
     + 0 comments

    for me its timing out for 3 cases. How to approach efficiently ?

  • adough99
     + 0 comments

    I was able to modify list A with the queries given, but I am stuck trying to find out the beautiful arrays.

    I've given the frequencies of each integer in array A but not sure what to do from there. So far I have {2 : 3, 1 : 2}but don't know how to find beautiful array from that