# 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.

150 questions
Filter by
Sorted by
Tagged with
1 vote
54 views

### Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
44 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 ...
1 vote
75 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 ...
39 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 ...
• 1
1 vote
104 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 ...
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 ...
1 vote
54 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 ...
1 vote
51 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 ...
1 vote
109 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 ...
• 45
1 vote
142 views

### Median of two sorted arrays

Two sorted arrays A and B are given having size l and m ...
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 ...
1 vote
109 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] ...
• 11
1 vote
63 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 ...
• 333
120 views

• 103
1 vote
59 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 ...
• 25
732 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 ...
• 225
174 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 ...
• 377
1 vote
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 ...
• 47
158 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?
• 101
1 vote
111 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 ...
• 11
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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$ ...
• 101
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 ...
141 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 ...
• 131
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-...
• 163
802 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 ...
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 ...
1 vote
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: ...
• 176
142 views

• 133
1 vote
197 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 ...
• 117
1 vote
### 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 ...
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 ...