Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [divide-and-conquer]

Divide-and-conquer is an algorithmic technique in which a problem is divided into smaller subproblems, whose solutions are combined to a solution of the original problem. Classical examples include mergesort, quicksort, and FFT.

Filter by
Sorted by
Tagged with
0 votes
1 answer
43 views

Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time. Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
inkwad's user avatar
  • 1
1 vote
1 answer
68 views

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

My question arises out of this competitive programming problem. The idea is to find a unique element $u$ and then divide-and-conquer for the subarray to the left and to the right of $u$. Searching for ...
Elucidase's user avatar
0 votes
2 answers
38 views

Recursive grid search of a sorted matrix

I have an algorithm that is checking whether the given key is present in the 2D sorted array where each row is sorted in an ascending order from left to right and ...
Yan's user avatar
  • 1
1 vote
1 answer
97 views

Quick sort with $K-1$ pivots

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
Haaziq Jamal's user avatar
0 votes
0 answers
23 views

Given two paths, how can I merge them in a Divide-and-Conquer algorithm to find the optimum earning route given a set of points with rewards?

The problem statement is the following: given a non-empty set P of (x, y) points with an associated reward, find the path through P that gives the maximum earning. The earning of a path is the sum of ...
synzgrsck's user avatar
1 vote
1 answer
52 views

Proof of correctness for Binary Search algorithm to find length of array for unknown length

For the algorithm provided in answer to this question, how would I go about proving the correctness of the algorithm? The referenced question is: “You are given an array $A$ of length $n$. Each value ...
Hugh Mann's user avatar
1 vote
0 answers
47 views

What are solutions to the convex hull problem?

I have researched multiple solutions to the convex hull problem, but I am afraid I don't really understand some of them. For example, Graham's scan is a bit confusing as it is not very clear if the n ...
user79644's user avatar
1 vote
1 answer
99 views

Restore the original array after merge Sort based on it's steps

i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left ...
vhd's user avatar
  • 45
1 vote
1 answer
129 views

Median of two sorted arrays

Two sorted arrays A and B are given having size l and m ...
Shashikant's user avatar
2 votes
0 answers
79 views

Implementation of the divide-and-conquer principle for a specific summation formula

I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
TreeBook1's user avatar
1 vote
1 answer
91 views

Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
patayala's user avatar
1 vote
1 answer
62 views

product of every difference

Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $ 10^9 + 7 $ $$ \prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7) $$ Best approach I can ...
bihariforces's user avatar
0 votes
1 answer
108 views

Substitution method for the upper bound of a recurrence without an explicit base case

Pages 90-91 of 'Introduction to Algorithms' (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence: $$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{...
user51462's user avatar
  • 123
2 votes
2 answers
99 views

Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows: **Algorithmic recurrences [...] A recurrence is algorithmic, if for every sufficiently large ...
user51462's user avatar
  • 123
0 votes
1 answer
92 views

What recurrence describes the time complexity of this algorithm?

The problem is as follows: The input is an array $A$ of $n$ natural numbers such that: (1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
Lucas Peres's user avatar
1 vote
1 answer
57 views

Minimum amount of parties containing round tables for everyone to meet each other

So the problem is: There is a group of n people that want to meet each other and everyone is divided into pairs, so everyone has a partner that they know. Now there will be parties at which they can ...
Tomyy's user avatar
  • 25
0 votes
1 answer
712 views

Finding majority element in $\mathcal{O}(nlogn)$ time

I am trying to build the logic behind a divide and conquer algorithm that will find the majority element in a matrix $A$ with $n$ elements in $\mathcal{O}(nlogn)$ time. I thought that in order to make ...
Tita's user avatar
  • 225
0 votes
1 answer
171 views

Why does merge sort work for any $n$, but the basic FFT algorithm only for powers of $2$?

Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $n$, the FFT algorithm given in CLRS (section 30.2, third ...
Rohit Pandey's user avatar
1 vote
2 answers
3k views

Closest pair of points in 3D

My professor mentioned that if we already know the divide and conquer algorithm for the closest pair of points in 2 dimensions it's easy to think of a similar algorithm for the 3 dimensions. But I am ...
Hjm's user avatar
  • 47
0 votes
1 answer
155 views

In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?

Let's say number of elements are a power of 4. Now if we break the array in parts of 1/4 and 3/4, how do we calculate the time complexity in this case?
Anmol Gupta's user avatar
1 vote
1 answer
106 views

$O(n \log n)$ Algorithm for first Train Problem

On $n$ parallel rails there are $n$ trains with constant speeds $v_1, ..., v_n$. At time $0$ the trains are at positions $k_1, ..., k_n$. Find an $O(n \log n)$ algorithm that determines which trains ...
spooni's user avatar
  • 11
0 votes
0 answers
100 views

Modification on Boyer Moore Algorithm to find an element that occurs more than n/3 times

Given an array of numbers with length $n=3^k$, we try to find an element that occurs more than $\frac{n}{3}$ times. So work as follow: We divide the array into 3 parts of equal length. Find ...
jhjhb's user avatar
  • 1
1 vote
1 answer
94 views

Envyless location using divide and conquer

We have a cake of length $n$ and we have two arrays $A$ and $B$ of size $n$. The two arrays have order like below. $A[0]<A[1]<\dots <A[n]$, $B[0]>B[1]>\dots >B[n]$. We define a ...
Andrew Kim's user avatar
8 votes
5 answers
3k views

Divide and Conquer to identify a knight from n people

So I am doing an exercise in which there are $n$ people who are either knight or rogue, more than $\frac{n}{2}$ are knights. You are a princess and would like to marry a knight and do not want to ...
AlgoManiac's user avatar
0 votes
1 answer
26 views

Termination condition for max of array using divide and conuqer approach

I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
user avatar
3 votes
1 answer
325 views

Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
Fred Jefferson's user avatar
0 votes
0 answers
188 views

Space complexity for divide-and-conquer

Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
user432944's user avatar
0 votes
0 answers
44 views

Closest pairs of points with conquer without divide approach

In an algorithm where I have to search for the pair of points in a plain, with the smallest distance: suppose that we want to use a "Divide and Conquer" approach. Is it possible to make it ...
Claudio Ferraro's user avatar
3 votes
0 answers
139 views

What are some examples of overlapping subproblems that don't have an optimal substructure thereby we cannot solve it using dynamic programming?

I believe problems like quicksort and other divide-and-conquer are problems that have optimal substructure but do no have any overlapping subproblems. I hope I'm correct here. But I'm unable to think ...
Srikanth's user avatar
  • 131
0 votes
1 answer
32 views

Recursive decomposition if a sequence can be parsed in both directions

Given a sequence/string of values and an algorithm that can process said sequence in both directions and obtain the same result - does it follow that the problem can in fact be decomposed in a divide-...
adrianton3's user avatar
-1 votes
3 answers
795 views

Find element with at least $\frac{n}{2}$ repeats in an array

I saw this question on my college "Design of Algorithms" exam but I could not solve it: Given an array $A[1..n]$ of integers. find an element which is repeated at least $\frac{n}{2}$ times ...
Ashkan Khademian's user avatar
0 votes
0 answers
106 views

Longest sequence of 1s in a binary matrix

I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
Pierre3990's user avatar
1 vote
1 answer
97 views

Is this divide-and-conquer algorithm O(n)?

Yesterday I came up with a divide-and-conquer algorithm about all subarrays of length k of an array of length n. Outline: ...
no comment's user avatar
3 votes
3 answers
141 views

Algorithms question: Largest contiguous subset selection

Q. Given two arrays, $A$ and $B$, of equal length, find the largest possible contiguous subset of indices $[i,j]$ such that $\max(A[i: j]) < \min(B[i: j])$. Example: $A = [10, 21, 5, 1, 3], B = [3, ...
David jones's user avatar
2 votes
1 answer
769 views

Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
joelsh's user avatar
  • 21
1 vote
2 answers
86 views

Minimal element in logarithmic time

Suppose $A$ is an array of distinct natural numbers. We call an element $A[i]$ minimal if it's less than both the element before and after it (if any). Present a worst-case $O(\log n)$ algorithm for ...
Emad's user avatar
  • 411
0 votes
1 answer
386 views

Multiplying two integers by dividing each into 3 parts

Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
Wais Kamal's user avatar
3 votes
3 answers
1k views

Clarification on the algorithm for finding a majority element

Here's a question about using a divide and conquer approach to find a majority element in an array. It's taken from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Question 2.23. I'm ...
user810228's user avatar
2 votes
1 answer
95 views

Calculate the number of "count inversions" of sub arrays

Recently, I encountered the following problem: Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find ...
competitive-programmer123's user avatar
0 votes
0 answers
73 views

Tangled cable - divide and conquer

Tangled cable: Let's have a long cable, from both ends of which protrudes n wires. Each wire at the left end is connected to just one at the other end and we want to find out which one. To do this, we ...
Rikib1999's user avatar
  • 125
0 votes
1 answer
302 views

Multiplication of polynomials in value representation as done for Fast Fourier Transform

I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ...
heretoinfinity's user avatar
0 votes
1 answer
896 views

A visitor at a political convention with n delegates

So I have been asked to specifically construct a divide and conquer algorithm for the question: "You are a visitor at a political convention with n delegates; each delegate is a ...
pk00's user avatar
  • 27
0 votes
1 answer
198 views

Divide and conquer problem:sequence of integers (with possible repetitions)

I was trying to solve this problem. Let $A[1] . . . , A[n]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A[i], A[i + 1], . . . A[j]$...
hcr2077's user avatar
  • 13
1 vote
1 answer
206 views

Divide and conquer algorithm for a gas station problem

I never heard about this variation of the gas station problem. The statement is as follows: There is just one road connecting the n+1 cities c0, …, cn consecutively. You want to go from c0 to cn ...
Norhther's user avatar
  • 117
1 vote
1 answer
738 views

Can the maximum single sell profit by divide and conquer be O(n)?

The single sell profit problem is: Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day. There is a solution ...
mike's user avatar
  • 121
3 votes
1 answer
207 views

Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
random_0620's user avatar
1 vote
1 answer
196 views

Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$

Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is ...
Ayush's user avatar
  • 117
1 vote
1 answer
110 views

Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$

Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a ...
errorcodemonkey's user avatar
0 votes
1 answer
106 views

Finding the base case for T(n) = T(n - a) + T(a) + cn

I was solving the recurrence using Recursion tree method: $$ T(n) = T(n - a) + T(a) + cn$$ When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the ...
Sachin Bahukhandi's user avatar
2 votes
1 answer
90 views

Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem: We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $...
Sachin Bahukhandi's user avatar