Dense Array codeforces solution

editorial
1

How i improve These Answer for less Memory and less time

#include<iostream>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,l=0;
		float z,x,m;
		cin>>n;
		int a[n];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		for(int i=0;i<n;i++)
		{	
			int j=i+1;
			if(j<n)
			{
				x=max(a[i],a[j]);
				m=min(a[i],a[j]);
				z=x/m;
				while(z>2)
				{
					m=m*2;
					z=x/m;
					l++;
				}
			}
		}
		cout<<l<<"\n";
	}
}
3

Every time there’s a pair of elements such that a>2*b, you need to insert elements between them, the number of inserted (or added) elements will be minimum when the elements would be of the form, a,a*2,a*4,a*8........b, that is a GP, with r=2, a as first term, and last term<=b and >=b/2.
So you need to add nearest integer less than log2(b/a), everytime you encounter such elements which do not satisfy the criteria.

1 Like