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…
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]))
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))
Yes my teammate solved that one using first method
Thanks
But It was accepted.
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
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.