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

141 questions
Filter by
Sorted by
Tagged with
24 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] ...
1 vote
42 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 ...
58 views

1 vote
48 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 ...
288 views

### Divide and conquer problem

Problem: Given a set of n intervals I = [a1, b1],[a2, b2], . . .[an, bn]. Here ai < bi for all i = 1 to n. Devise a Divide and Conquer algorithm to compute the length of the biggest overlap between ...
351 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 ...
145 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 ...
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 ...
133 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?
1 vote
86 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 ...
95 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
88 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<A<\dots <A[n]$, $B>B>\dots >B[n]$. We define a ...
2k 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 ... 304 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 ...
176 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$ ...
35 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 ...
129 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 ...
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-...
638 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 ...
105 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
94 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: ...
139 views

1 vote
192 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 ...
1 vote
102 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 ...
87 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 ...
89 views

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 $... 0 votes 1 answer 166 views ### Sum weighted nodes between nodes in a DAG efficiently Suppose we have a directed acyclic graph$G=(V,E)$, such that all vertices have a addible weight, e.g. there is a function$weight: V \to \mathbb{R} $. Moreover two vertices$v,w \in V$are given and ... 0 votes 1 answer 23 views ### How to represent a recurrence that increments by one at each tree level? I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ I ... 1 vote 1 answer 95 views ### Runtime of Divide and Conquer Flavored Bogo Sort Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively. https://en.... 0 votes 2 answers 129 views ### "Low-High" sort divide and conquer with merge... how small to make the subproblems for good efficiency? For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So ... 1 vote 1 answer 349 views ### CLRS closest-pair$L_m\$ distances

I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following: We can define the distance between two points in ways other than euclidean. In the ...
84 views

### Simple Divide and conquer proof

Suppose a simple program is reading messages from a distributed cluster. The cluster has 3 partitions, and the program has three readers that are assigned one partition each (The setup will always be ...
1 vote