Need Help!

How can we find out the number of unique HCFs among all non-empty subsequences of the given array?
Problem -Link

1 Like

Problem link ?

The maximum HCF of a subsequence will be less than or equal to the maximum value in the array. So you can traverse from 1 to max_value and check if it is HCF of any subsequence or not.

The idea is pretty simple just check for all possible candidates of gcd naively. I’m attaching the code, feel free to ask if you don’t get the idea.

#include "bits/stdc++.h"
using namespace std ; 
const int mxA = 2e5,mxN=1e5 ;
int d[mxA+1] ;
int main(){
  int n  ;
  cin >> n  ;
  vector<int>a(n) ;
  for(int &x:a)
    cin >> x ;
  set<int>ok(a.begin(),a.end()) ;
  for(int i=1;i<=mxA;i++)
    for(int j=i;j<=mxA;j+=i)
      if(ok.count(j))
        d[i]=__gcd(d[i],j) ;
  int ans =0 ;
  for(int i=1;i<=mxA;i++)
    ans+=d[i]==i ;
  cout << ans ;
}

Time complexity is \mathcal{O}(MlogM) where M is the max element.

T(M)=M(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+ \cdots) =MlogM
2 Likes

Cud you please explain this part of the code as to what are you doing?

Like I understood you are trying to something with max value of the array but still isn’t clear how are u checking the gcd part? What will be initial value of array d is it zero because i’m not sure it may contain garbage value also right?

d[i] is the gcd of all multiples of i which are present in the array.

And this block of code does the same.
Basically, idea is that gcd of all multiples of a number i which are present in the array will be at least i and if it’s exactly i then we can safely conclude that i will be gcd of some subsequence.

Also default value of d[i] is 0. Because d is a global array and in c++ global arrays are initialized with 0 by default.

1 Like

@cubefreak777 Thanks a lot!

1 Like

I see you participated in CognoAI

1 Like

Here is the contest link , which is obviously over. Programming Problems and Competitions :: HackerRank

:sweat_smile:

How about the matrix one ?

I was only able to solve one problem. :sweat_smile:

Same here :frowning: .

@ilovepenguins please inform me if you get solution of matrix problem.

for the matrix ques we can check like which L shape the number will belong to first by taking sqrt of k. After getting L shape I guess you can just sort comfortably i guess that L shaped array and find the desired number.
By L shape i mean something like this:

1 2 3
2
3

I am taking sqrt of k because the diagonal element in the L shape is smallest number in the L shape

Crack the Code by CognoAI . Cubefreak tried to explain it to me.

1 Like