Click here to Skip to main content
15,892,797 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Quote:

You are given a sequence A1,A2,…,AN. For each valid i, the star value of the element A[i] is the number of valid indices j[__i and A[j] divided by A[i].


i have used merge sort in place of insertion which i was using earlier but still no effect on TLE error.

What I have tried:

C++
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
#include<stdio.h>         
void Merge(int *a, int low, int high, int mid)
{
	// We have low to mid and mid+1 to high already sorted.
	int i, j, k, temp[high-low+1];
	i = low;
	k = 0;
	j = mid + 1;
 
	// Merge the two parts into temp[].
	while (i <= mid && j <= high)
	{
		if (a[i] < a[j])
		{
			temp[k] = a[i];
			k++;
			i++;
		}
		else
		{
			temp[k] = a[j];
			k++;
			j++;
		}
	}
 
	// Insert all the remaining values from i to mid into temp[].
	while (i <= mid)
	{
		temp[k] = a[i];
		k++;
		i++;
	}
 
	// Insert all the remaining values from j to high into temp[].
	while (j <= high)
	{
		temp[k] = a[j];
		k++;
		j++;
	} 
 
	// Assign sorted data stored in temp[] to a[].
	for (i = low; i <= high; i++)
	{
		a[i] = temp[i-low];
	}
}
 
//  to split array into two parts.
void MergeSort(int *a, int low, int high)
{
	int mid;
	if (low < high)
	{
		mid=(low+high)/2;
		// Split the data into two half.
		MergeSort(a, low, mid);
		MergeSort(a, mid+1, high);
 
		// Merge them to get sorted output.
		Merge(a, low, high, mid);
	}
}


int main()
{
	int t,i,j,k,max[100011],T,n[10],A[100011],c[100011];
	cin>>t;
	
	for(i=0;i<t;++i)
	{ 
		cin>>n[i];
		T=n[i];	
				
		for(j=0;j<n[i];++j)
		{
			cin>>A[j];
		}		
				
		for(j=0;j<n[i];++j)
		{ 
		  c[j]=0;
			
			for(k=0;k<j;++k)
			{ 
			  if(A[j]!=0)
			  {
			  	if(A[k]%A[j]==0)
			    {c[j]++;
			
			    }
			  }			
		    }
		}
		
		 MergeSort(c,0,T-1);
		 max[i]=c[T-1];						
	}	
	
	for(i=0;i<t;++i)
	{
	    cout<<max[i]<<"\n";
	}
	return 0;
}
Posted
Updated 4-Oct-19 22:36pm
v5
Comments
CPallini 5-Oct-19 3:21am    
What are your requirements (you reported only the constraints on the input data)?
[no name] 5-Oct-19 3:27am    
You are given a sequence A1,A2,…,AN. For each valid i, the star value of the element A[i] is the number of valid indices j
Patrice T 5-Oct-19 3:44am    
Use Improve question to update your question.
So that everyone can pay attention to this information.

You should give a link to full requirement.
and re-show your code.
[no name] 5-Oct-19 3:54am    
i have to calculate number of valid indices such tha j
Patrice T 5-Oct-19 3:56am    
and what is a "valid indice" ?
You should give a link to full requirement.

1 solution

Quote:
i don't know which part is causing TLE error

A TLE is a Time Limit Error, this mean that the whole program takes too long to execute.
In other words, your algorithm is too complicated or too simple minded.

There is more than 1 solution to given problem, but we can't appreciate what your program is doing because you forgot to tell us what problem you try to solve.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900