How can I decrease the time which is used in this code?

Question

0.00/5 (No votes)

See more:

Hello. The goal of this problem is to represent a given positive integer 𝑛 as a sum of as many pairwise distinct positive integers as possible. That is, to find the maximum 𝑘 such that 𝑛 can be written as 𝑎1 + 𝑎2 + · · · + 𝑎𝑘 where 𝑎1, . . . , 𝑎𝑘 are positive integers and 𝑎𝑖 ̸= 𝑎𝑗 for all 1 ≤ 𝑖 < 𝑗 ≤ 𝑘.
Here is my code:

C#

static long[] MaximumNumberOfPrizes(long n)
{
    if (n == 1)
    {
        return new long[]{1};
    }
    long tmp = n;
    long sum = 0;
    int m = 1;
    List<long> mylist = new List<long>();

    for (long i = n; i > 0; i--)
    {
        if (sum >= tmp)
        {
            break;
        }
        n = n - m;
        if (n <= 0)
        {
            break;
        }
        sum = sum + m;
        if (mylist.Contains(m))
        {
            m++;
        }
        else
        {
            mylist.Add(m);
            m++;
        }
    }

    long total = mylist.Sum(s => Convert.ToInt64(s));
    if (total == tmp)
    {
        return mylist.ToArray();
    }

    else
    {
        long rem = tmp - total;
        long max = mylist.AsQueryable().Max();
        if (mylist.Contains(rem))
        {
            mylist.Remove(max);
            mylist.Add(max + rem);
        }
        else
        {
            mylist.Add(rem);
        }
    }
    return mylist.ToArray();
}

And in

C#

Main

C#

int n = Convert.ToInt32(Console.ReadLine());
            long[] myarray = MaximumNumberOfPrizes(n);
            System.Console.WriteLine(myarray.Length);
            for (int i = 0; i < myarray.Length; i++)
            {
                System.Console.Write(myarray[i] + " ");
            }

What I have tried:

When I submit my code the test case which is related to the time limit fails:

Failed case #35/42: time limit exceeded (Time used: 3.08/1.50, memory used: 26767360/2147483648.)

I think because of the operations on the list my code works slowly. But I don't know how to decrease the Big-O of my code. Actually, I don't want to change my code a lot because the algorithm is correct but it is slow.
I will be grateful for your help and advice. Thanks.

Posted 30-Sep-21 4:10am

Aylin Naebzadeh

Updated 3-Oct-21 1:54am

Add a Solution

Comments

PIEBALDconsult 30-Sep-21 11:39am

Don't use Linq
Don't use lambdas
Don't use Convert.ToInt32
Don't use Convert.ToInt64
Don't use .ToArray()
Don't use .Contains
...

Aylin Naebzadeh 30-Sep-21 18:45pm

I thought that LINQ and lambdas are faster than for and foreach, but now I understand they are in this case slower and actually they have a hidden loop. And in fact the biggest advantage is that they are easy to read.

PIEBALDconsult 30-Sep-21 18:47pm

Yes, readability at the cost of performance.

Dave Kreskowiak 3-Oct-21 11:34am

LINQ is nothing but syntaxic sugar, meaning it's a shorthand way of expressing a larger, standardized block of code, that does the job for you. It does NOT make anything faster.

Aylin Naebzadeh 6-Oct-21 16:44pm

That's right👌

Dave Kreskowiak 3-Oct-21 11:36am

You updated the code in the question, but you're still thinking in terms of "brute force" solutions. You have to rethink your entire approach and come up with an entirely new algorithm that does not depend on broad searching for a solution.

Aylin Naebzadeh 6-Oct-21 16:44pm

Actually, I did not update it🤔.

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Dave Kreskowiak · Answer 1 · 2021-09-30T04:16:00

Solution 1

You have to rethink your approach to the problem. Challenges like this are setup so the straight forward approach you are using will always be too slow to beat the time constraint.

There's more than one way to approach this problem and that's the point behind the challenge.

Posted 30-Sep-21 4:16am

Dave Kreskowiak

Comments

Aylin Naebzadeh 30-Sep-21 10:26am

Yes, I have to think more about it.

OriginalGriff · Answer 2 · 2021-09-30T04:19:00

Solution 2

Quote:
Actually, I don't want to change my code a lot because the algorithm is correct but it is slow.

And there is your problem.
It's not the code that is slow, but the whole way your are doing it - brute force.

The whole idea of code challenges is not to just get it working, but to do it elegantly, so that it isn't a brute force approach.
You need a better algorithm, then better code to implement that.

Posted 30-Sep-21 4:19am

OriginalGriff

Comments

Aylin Naebzadeh 30-Sep-21 10:25am

You are right. I will think more about it.

OriginalGriff 30-Sep-21 11:05am

Excellent!

Luc Pattyn · Answer 3 · 2021-09-30T05:26:00

That takes less than one millisecond!

1) The largest k will be achieved by using the smallest possible a-values.
2) The sum S(x) of 1,2,3,...,x equals x*(x+1)/2
3) You can find the smallest x that satisfies S(x)>=n with a simple square root plus some extra check
4) finally, if S(x) exceeds n by d, then drop the a-value that equals d !!!

Hence, you don't need any loops, lists, arrays, whatever, to solve the problem. A few simple formulae are all it takes. You will only need one array and one loop to stuff the solution in the format the API specified.

And yes, that basically means throwing away all of your code no matter how correct it may be.

Perić Željko · Answer 4 · 2021-10-03T01:54:00

To find max k with brute force or by quadratic equasion and print numbers with console application:

using System;

namespace Code_project_answer
{
	class Program
	{
		public static void Main(string[] args)
		{
			Console.WriteLine(" Hello World! ");
			Console.WriteLine(" ************ ");
			
			Console.Write(" n = ");
			int n = int.Parse(Console.ReadLine());
			Console.WriteLine(" ************ ");
			
			int k = 0;
			int i = 0;
			
			//
			// For next loop
			//
			Console.WriteLine(" for..next ");
			Console.WriteLine(" ************ ");
			
			for (i = 1; i <= n; i++)
			{
				k += i;
				if (n <= k + i)
				{
					k = i;
					Console.WriteLine(" k = " + k.ToString());
					Console.WriteLine(" ************ ");
					break;
				}
			}
			
			//
			// While loop
			//
			Console.WriteLine(" while loop ");
			Console.WriteLine(" ************ ");
			i = 0;
			k = 0;
			while (n > k + i)
			{
				i++;
				k += i;
			}
			
			k = i;
			
			Console.WriteLine(" k = " + k.ToString());
			Console.WriteLine(" ************ ");
			
			//
			// Use quadratic equasion
			// a*x^2 + b*x + c = 0;
			//
			Console.WriteLine(" Quadratic equasion ");
			Console.WriteLine(" ****************** ");
			
			int a = 1;
			int b = 1;
			int c = -2 * n;
			
			int d = (b * b) - (4 * a * c);
			
			if (d >= 0)
			{
				int x1 = (-b + ((int)Math.Sqrt(d))) / 2 * a;
				int x2 = (-b - ((int)Math.Sqrt(d))) / 2 * a;

				Console.WriteLine(" x1 = " + x1.ToString());
				Console.WriteLine(" x2 = " + x2.ToString());
				Console.WriteLine(" ************ ");
				
				k = x1;
				
				Console.WriteLine(" k = " + k.ToString());
				Console.WriteLine(" ************ ");
			}
			else
			{
				Console.WriteLine(" There is no solution for quadratic formula. ");
				Console.WriteLine(" ******************************************* ");
			}
			
			//
			// Print one of many possible combinations
			//
			int ln = 0;
			ln = n - (((k - 1) * k) / 2);
			Console.Write(" " + ln);
			k--;
			while (k > 0)
			{
				Console.Write("+" + k);
				k--;
			}
			Console.WriteLine();
			Console.WriteLine(" ************ ");
			
			Console.Write("Press any key to continue . . . ");
			Console.ReadKey(true);
		}
	}
}

All the best,
Željko Perić

How can I decrease the time which is used in this code?

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0