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

Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

7,639 questions
Filter by
Sorted by
Tagged with
34 views

An underestimated tradeoff between Memory and the Effectivity of Computation?

Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form ...
16 views

Time complexity of linear iteration bounded by logarithmic iteration?

I was wondering about the time complexity of something like the following loop (where work() is O(1)): ...
23 views

Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the ...
43 views

Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

Here's the start and the vernacular I'm using. ...
20 views

Help with Linear recurrence relation with balanced partition

In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with "partizione bilanciata" which means "balanced partition". My course ...
44 views

Range Query with conditions

Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the ...
47 views

is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.
16 views

Algorithm for coherent motion. Which bus is app user on?

I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on. To achieve this I am working on building a function ...
25 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
78 views

Given $n=pq=a^2+b^2$, can we factor $n$?

Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$? It is a known ...
58 views

Minimum index Array Product

Given an array A(1 indexed based) of positive integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(...
41 views

I want to solve this question for algorithm, please [closed]

Write an algorithm that calculates the monthly payment of a bank loan with a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of years to pay the loan, you can ...
35 views

How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book: I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
33 views

How to move spheres in 3d without collision

Is there an algorithm that gets as an input 2 arrays (arr_origin, arr_dest) that represent spheres with a set radius (R) in a 3d space, (x,y,z) points. And finds a route for the spheres from origin to ...
43 views

Guess the number from its different base representations

Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or ...
94 views

How to query the tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each ...
39 views

30 views

Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?

Imagine trying to pick a random number from a pool of numbers that contains: i1 times the number 1 i2 times the number 2 i3 times the number 3 ... etc For example picking a random number in a ...
21 views

How to find a path in maze with navigator physical size constraints?

Assuming a 2D maze, how would one go about solving it for rigid 2D object moving through it? Additional specification: The object shape - it is a single entity, not a swarm/fleet. A shape of ...