The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [time-limit-exceeded]

When the code scales so poorly in the face of large inputs that it cannot complete in a reasonable amount of time, use this instead of the [performance] tag.

Filter by
Sorted by
Tagged with
10
votes
3answers
574 views

Optimization on Sieve of Eratosthenes using vector<bool>

I am solving this prime generator problem from SPOJ: Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers! ...
10
votes
1answer
1k views

“Mixing Proteins” HackerRank challenge

I am doing this problem on HackerRank and I'm failing test cases because it's taking too long to run when n and k get over 8000. I believe the dictionary lookup should be \$O(1)\$ while lists are \$O(...
10
votes
1answer
918 views

Programming Challenge from Kattis: Apparatus

I am trying to solve apparatus problem, paraphrased below. There is an apparatus with n on/off switches with a one-to-one correspondence to n lights (but with an unknown permutation). We have ...
10
votes
2answers
556 views

Minimum sub-array challenge

Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
10
votes
1answer
956 views

Scanning multiple huge files in Python

I'm trying to implement an algorithm able to search for multiple keys through ten huge files in Python (16 million of rows each one). I've got a sorted file with 62 million of keys, and I'm trying to ...
10
votes
2answers
374 views

Project Euler Problem 530: sum of sum of greatest common divisors

Here is a description of Project Euler problem 530: Every divisor \$d\$ of a number \$n\$ has a complementary divisor \$n/d\$. Let \$f(n)\$ be the sum of the greatest common divisor of \$d\$ ...
10
votes
2answers
627 views

Finding all contiguous sublists such that each member appears an even number of times

The program needs to find all contiguous sublists of numbers where the number of occurrences of every member in the contiguous sublist is divisible by 2. The first line of input is N (the number of ...
10
votes
1answer
162 views

Determining position of point W.R.T to given line equation

Problem from HackerRank:: Problem Statement: There are \$N\$ lines. Each line has an index between \$1\$ and \$N\$. The slope of each line is negative, i.e. it goes from upper-left to lower-...
10
votes
1answer
164 views

Using bisect to flip coins

I am trying to solve this problem on Codechef, which has a list of \$N\$ coins, all initially tails-up, and a list of \$Q\$ commands. There are two possible commands, ...
10
votes
1answer
383 views

Parallelogram Connectivity

This is the hardest problem from the HackerRank contest University CodeSprint 2. Problem Statement Consider a hexagonal board with \$ n \times m \$ cells where each cell is black or white. The ...
9
votes
4answers
1k views

Compute binary XOR of all integers in a range, mod 2

here I am taking 3 inputs. 1st input will take test cases and the other two input will take starting and ending range. the program is running fine as expected but the limit of this question for ...
9
votes
4answers
2k views

A faster way to compute the largest prime factor

I am self-learning js and came across this problem(#3) from the Euler Project The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? ...
9
votes
4answers
4k views

Finding the maximum element of a Stack

I have been solving this problem of Hackerrank recently .. https://www.hackerrank.com/challenges/maximum-element A little bit about the problem You have an empty sequence, and you will be given N ...
9
votes
3answers
4k views

Odd divisor summation

Given an integer, k, we define its odd divisor sum to be the sum of all k's odd divisors. For example, if k = 20, then the odd divisor sum would be 1 + 5 = 6. Similarly, if given an array of values, ...
9
votes
2answers
560 views

List elements digit difference sort

I am doing a code challenge of codesignal.com which ask for following things: Given an array of integers, sort its elements by the difference of their largest and smallest digits. In the case of a tie,...
9
votes
3answers
4k views

3n + 1 problem optimization

The problem can be viewed here, since it's styled. I don't think I should just copy and paste. I implemented recessive function and dynamic programming to solve it. It can successfully passed UVa ...
9
votes
3answers
1k views

3n + 1 programming challenge in Python

I am trying to find a efficient solution for the 3n + 1 problem on uvaonlinejudge. The code I have uses memoization using a dictionary. I am getting a 'Time limit Exceeded' error when I submit the ...
9
votes
2answers
266 views

Project Euler #119 : Digit power sum

From problem #119 of the Project Euler : The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number ...
8
votes
5answers
5k views

Euler #3 largest prime factor

Problem Statement This problem is a programming version of Problem 3 from projecteuler.net The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of a given number N?...
8
votes
4answers
1k views

Project Euler problem 14 (longest Collatz sequence) in Swift 3

I was trying to solve Project Euler:Problem 14 using Swift 3, but it takes ages to give me an answer, which is a sign that my code is absolute garbage performance-wise. What could I do to increase the ...
8
votes
5answers
392 views

Pizza Hut math problem #1 in Haskell

I'm currently attempting to learn Haskell after a fair history of imperative programming. When I saw the Pizza Hut Pi Day math problems, I thought the first one would be a good candidate for my ...
8
votes
5answers
812 views

Counting pairs of integers whose sum is less than a given threshold

Recently I was going through this codechef problem while practicing for the upcoming zoc. The problem asks to calculate number of combinations of the given numbers where the sum is less than another ...
8
votes
3answers
232 views

Find the smallest positive integer that is absent from a given array

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
8
votes
3answers
1k views

Telling the length of the highest common substring between 2 words

This takes two strings and returns the length of the largest common substring. Example: contando_sstring_igual("abcdef", "cdofhij") # 2 Because the longest ...
8
votes
3answers
580 views

Phone number duplication detector

I am doing the POJ 1002 question. My code works fine but the website says the compilation time is more than 2000ms, which is not accepted. How can I improve my time-wise performance? Problem ...
8
votes
2answers
684 views

Balanced centrifuge configurations

Given an input N as the size of a centrifuge, I need to find out the number of balanced configurations. The full description is here. Centrifuge is a piece of ...
8
votes
3answers
2k views

Given a set of points and pairs of lines, count the number of points that are between the pairs of lines

This is a contest problem. The entire description is here. In resume: The question gives a point simulating a light explosion that always has a negative x coordinate, a set of pairs line segments on ...
8
votes
2answers
2k views

Finding an element in an array that occurs a given number of times

I am trying to solve the below problem from an online coding site: Fredo is pretty good at dealing large numbers. So, once his friend Zeus gave him an array of N numbers, followed by Q queries ...
8
votes
2answers
514 views

HackerRank Sherlock and Squares: count perfect squares in an interval

I've exceeded the time limit on Sherlock and Squares on hackerrank.com. Problem Given the number of test cases and a range (inclusive), find the number of numbers within that range that are perfect ...
8
votes
1answer
289 views

Calculating the Average Minimum Length of Random Numbers From 0 - 1 that Adds up to Greater Than 1

My Computer Science teacher gave us a task to calculate the average after one billion trials. His exact assignment was this: Consider generating a sequence of random numbers on the interval [0, 1) ...
8
votes
2answers
3k views

HackerRank leaderboard challenge

I have been doing this challenge in which I need to determine and return one's (i.e. alice) rank on a leaderboard by comparing her scores to the others'. I made ...
8
votes
2answers
188 views

Find two integers with the largest sum within a budget (breaking ties by smallest difference)

The algorithm finds a number pair that is as close to budget as possible, and if there are more pairs with same value, the pair with the least difference shall be given out. My algorithm works ...
8
votes
1answer
208 views

Find “prime polynomials” for a user's given prime, bounds, and degree

Very amateur programmer and first-time poster here. The program I wrote asks the user for a prime number, a lower and upper bound, and a degree (all of these are integers). I want to generate a list ...
8
votes
2answers
2k views

Given a collection of points on a 2D plane, find the pair that is closest to each other

Full disclosure: I'm working on this for an online course. However, my goal is really just to get a pointer to where the issue is. The goal is to implement the closest points problem, that is, given ...
8
votes
1answer
303 views

Beginner's attempt for Project Euler problem 12 (highly divisible triangle number)

I'm a couple weeks into learning Python and I'm working through the Project Euler problems. Problem 12 asks: What is the value of the first triangle number to have over five hundred divisors? My ...
8
votes
1answer
63 views

Search father (x) of the number D(x) and measure time and memory consumed

We define function D(x) as following: D(x) = x + sum of digits of x + sum of prime factors of x then call x the father of D(x) Write a program that gets input ...
8
votes
3answers
2k views

Leetcode 56: Merge Intervals

Problem statement Given a collection of intervals, merge all overlapping intervals. For example: Given \$[1,3],[2,6],[8,10],[15,18]\$, return \$[1,6],[8,10],[15,18]\$. My ...
8
votes
1answer
214 views

Convert an image into characters and colors for the windows console

I've written a function to convert an image into characters and colors for the windows console. At the moment the calculation takes about 13 seconds with a 700x700 pixel image but that time is ...
8
votes
1answer
173 views

Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
8
votes
2answers
126 views

Matching query patterns with previously stored strings

Program description The goal of this program is to get a number, which is the number of lines of inputs (lets call that number N) that the program will receive. Then the following N lines will ...
8
votes
1answer
435 views

Google FooBar “Prepare The Bunnies Escape”

I'm currently working through the google FooBar challenge, and I'm on the third level, in which I have to find the distance between the top left and bottom right points on a grid. The grid is filled ...
7
votes
3answers
1k views

The Next Palindromic number

I have incremented an integer in the function nextpalin() and converted it into a std::string for finding whether it's a ...
7
votes
5answers
2k views

Removing the largest values encountered so far in a list

The problem is, in summary: A set of values will be given. Whenever the input is -1, the largest number from the values inputted until then needs to be printed, and is then deleted. Here is the ...
7
votes
3answers
1k views

Given an integer s and a list of integers ints finding (x,y) in ints such that s = x + y

The following function sum_pairs(ints, s) takes two inputs: ints is a list with integer values and ...
7
votes
4answers
1k views

Code for calculating citizens beheaded

Recently I came across this problem , A despotic king decided that his kingdom needed to be rid of corruption and disparity. He called his prime minister and ordered that all corrupt citizens ...
7
votes
3answers
576 views

Counting the triangles that can be formed from segments of given lengths

Problem Statement: Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as lengths of three sides of triangles. ...
7
votes
3answers
516 views

Counting points on a given irregular grid that are inside or outside a circle

Given some points that are represented as (X, Y) coordinates, my task is to count the points that are inside a circle, on the circle, and outside the circle. The input is given in the following way: ...
7
votes
4answers
5k views

Hacker Rank - Poisonous Plants

I have the solution for the problem, but it is taking me 7 seconds to run on a large dataset. I am trying figure out a better way of doing this. It has to run in under 3 seconds. Problem Statement: ...
7
votes
3answers
364 views

Counting ways to choose vertices that form a right triangle

Croatian Open Competition in Informatics, contest 3, December 8, 2007 4. DEJAVU \$N\$ points are placed in the coordinate plane. Write a program that calculates how many ways we can choose ...
7
votes
1answer
1k views

Python program to find a word ladder transforming “four” to “five”

I saw this Puzzling problem and thought I would try to write a Python program to solve it. The task is to transform "four" to "five", forming a new four-letter word at each step, replacing one letter ...