CODEWITHSUNDEEP
c#console-applicationtime-complexity
Aarthna Maheshwari
Aarthna Maheshwari

Reputation: 169

Reducing time complexity of the code

I have the following code but it takes 20sec to process the 52957 inputs of type BigInteger. This is the question that i want to solve https://www.hackerearth.com/problem/algorithm/girlfriends-demands/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace girldfriends_demands
{
    class Program
    {
        private static string inputString = String.Empty;
        private static int testCases=0;
        private static BigInteger[,] indexArray;
        static void Main(string[] args)
        {
            initialize();
            printDemand();
            Console.ReadLine();
        }
        private static void initialize()
        {
            inputString = Console.ReadLine();
            testCases = int.Parse(Console.ReadLine());
            indexArray = new BigInteger[testCases, 2];
            for (int i = 0; i < testCases; i++)
            {
                string[] tokens = Console.ReadLine().Split();
                indexArray[i, 0] = BigInteger.Parse(tokens[0]);
                indexArray[i, 1] = BigInteger.Parse(tokens[1]);
            }
        }

        private static void printDemand()
        {
            char[] convertedString = inputString.ToCharArray();
            for (int i = 0; i < testCases; i++)
            {

                BigInteger length=inputString.Length;
                BigInteger startf, endf; ; 
                BigInteger.DivRem(indexArray[i, 0] - 1,length,out startf);
                BigInteger.DivRem(indexArray[i, 1]-1,length,out endf);
                char c=convertedString[((int)startf)];
                char e=convertedString[((int)endf)];
                if(c==e)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
        }
    }
}

Please specify how to reduce the time complexity of the code.This program gets the letters at the specified position in a string and prints true if they are same else false. Also computing the range at prior to the loop isn't helping

Upvotes: 1

Views: 1003

Answers (4)

Luaan
Luaan

Reputation: 63732

Console.ReadLine().Split()

is the biggest of your problems. For every single line in the file, you create an array of strings, one letter per string. This is a huge performance drain, and almost certainly not what you intended - in particular, it would be wholy unnecessary to use BigInteger to store a single-digit number...

I assume that you actually want to split the line in two based on some delimiter. For example, if your numbers are separated by a comma, you can use

Console.ReadLine().Split(',')

Even then, there is little reason to use BigInteger at all. The operation you're trying to perform is distinctly string-based, and very easy to do with strings. However, I can't really help you more specifically, because your problem description is incredibly ambiguous for such a simple task, and the code is so obviously wrong it's entirely useless to guess at what exactly you're trying to do.

EDIT:

Okay, your link confirmed my assumptions - you are massively overcomplicating this. For example, code like this will do:

var word = Console.ReadLine();
var items = int.Parse(Console.ReadLine());

for (var _ = 0; _ < items; _++)
{
    var indices = 
          Console.ReadLine()
           .Split(' ')
           .Select(i => (int)((long.Parse(i) - 1) % word.Length))
               .ToArray();

    Console.WriteLine(word[indices[0]] == word[indices[1]] ? "Yes" : "No");
}

First, note that the numbers will always fit in a long, which allows you to avoid using BigIntever. Second, you need to use Split properly - in this case, the delimiter is a space. Third, there's no reason not to do the whole processing in a single stream - waiting for the whole input, collecting it in memory and then outputting everything at once is a waste of memory. Fourth, note how easy it was to avoid most of the complex checks while incorporating the whole necessary mechanism in simple arithmetic operations.

This runs under 2 seconds on each of the input data, only using ~80kiB of memory.

I think that ideologically, this fits the site perfectly - it's very simple and straightforward and works for all the expected inputs - the perfect hack. Of course, you'd want extra checks if this was for an end-user application, but the HackerEarth site name implies hacks are what's expected, really.

Upvotes: 3

Arash
Arash

Reputation: 885

Myabe by removing casts in these line and using string.compare you cand decrease execution time 

            if(string.Compare(startf.ToString(), endf.ToString()))
            {
                Console.WriteLine("Yes");
                continue;
             }
                Console.WriteLine("No");

Upvotes: 0

bot_insane
bot_insane

Reputation: 2604

Why you use BigInteger ? In any case string.length is typeof int. It mean that if your string exceed 2147483647 (2^31 -1) your program will be broken.

I think changing BigInteger to int will help.

Upvotes: 4

Lee White
Lee White

Reputation: 3719

In my experience, frequent Console.WriteLine calls can lead to huge execution times.

Instead of calling that function whenever you want to add some output, I think you should use a StringBuilder object, and append all your output to it. Then, after the for-loop, call Console.WriteLine once to print the StringBuilder's contents.

This might not be your program's biggest problem, but it will help quite a bit.

Upvotes: 1

Related Questions