Count all special element question (Help)

Can anyone please help me with the approach of this problem its from hacker earths contest which ended today 11:55 PM

Please Give the Link of the problem so i can help u better…:slight_smile:

@ssrivastava990 Its from Hacker Earth contest the link to question

a[]
f[]
for(int i=0;i<n;i++)
{
for(int j=1;j<=sqrt(a[i]);j++)
if(a[i]%j==0)
f[j]++,f[a[i]/j]++;
}
ll ans=0;
for(int i=1;i<=n;i++)
if(f[i])
ans+=f[i];

cout<<ans;

Time Complexity O(n*sqrt(max(a[i]))

1 Like

@yaman_47 it can be done in O(N*log(max (a[i])))

unordered_map a[]
unordered_map f[]
maxa=max(a[i])
for(int i=1;i<=n;i++)
for(int j=i;j<=maxa;j+=i)
{
if(a[j])
f[i]++;
}
ll ans=0;
for(int i=1;i<=n;i++)
if(f[i])
ans+=f[i];

cout<<ans;

time complexity:- o(maxalog(n))

@yaman_47 Bro was your code accepted completely …???

Yes my teammate solved that one using first method

Thanks
But It was accepted.:grinning:

Bro ans += f[i] i think

Sorry.
Yes you are right

@yaman_47 Thanks bro i got your first code and found what i was doing wrong and can you explain little bit your second code :blush:

package codechef;

import java.util.Scanner;

public class count {

public static void main(String[] args) {
  Scanner scan=new Scanner(System.in);
     int i;
     int count = 0;
	System.out.println("Enter Array size");
	int n=scan.nextInt();

	System.out.println("Enter Array Elements");
	int[] ar=new int[n];
	for( i=0;i<ar.length;i++)
	{
		 ar[i]=scan.nextInt();
	}
	for( i=1;i<=ar.length;i++)
	{
		for(int j=0;j<ar.length;j++)
		{
			if(ar[j]%i==0)
			{
                 count++;
			}
		}
			
	}
	System.out.println("Total count= "+count);
}

}

Can you please explain what are you doing here.