# Questions tagged [divide-and-conquer]

Divide and conquer is an algorithm design paradigm based on recursion. A problem is broken down into multiple small subproblems until they are simple enough to be solved. The solutions are then combined to give a solution to the original problem.

34 questions
Filter by
Sorted by
Tagged with
1 vote
145 views

### Duplicate Binary Search Improvements

I'm working on an implementation of binary search (in Python) that can operate on a sorted array that may have duplicate elements. I've written a submission that has managed to hold up against my test ...
12 views

### Closest pair of points algorithm [duplicate]

My program needs to find the closest pair of points within a list of points. I can't import any libraries apart from the ones I have. I use the well known Divide and Conquer method. ...
• 11
1 vote
113 views

### Closest Pair of Points - Optimizing Code for big sets of points

I'm trying to create an algorithm that finds the closest pair of points (2D) within a set of points. I'm using a divide and conquer method which is explained here Closest Pair of Points Algorithm. ...
• 11
245 views

### Karatsuba's multiplication

I am working my way through an algorithms course online, and the assignment is to implement Karatsuba's multiplication algorithm. I am also trying to practice C++, so I wanted to implement it in that ...
• 135
1k views

### Finding the majority element in an array

A list is said to have a “majority element” if more than half of its entries are identical. In this classical problem the goal consists of determining whether a list a of length n has a majority ...
• 393
2k views

### Writing my first binary search by myself

Is there any way in which I can improve my code? I don't know if it is 100% right, and if it can be tweaked in order to be more efficient. That's why I'm posting here. I'm open to any suggestions :) <...
100 views

### Divide and Conquer Password Bruteforcer

My program brute-forces a password. The password is a string composed of a key and a four digit numeric code. The key is known so we are basically brute-forcing between 0000 through to 9999 An example ...
• 247
101 views

### Max Contiguous Subarray: Divide and Conquer

I am conversant with Kadane's Algorithm. This is just an exercise in understanding divide and conquer as a technique. Find the maximum sum over all subarrays of ...
• 173
143 views

### Maximum sub-array sum

My code finds the maximum subarray sum and the starting and ending index of that subarray. ...
• 41
10k views

### Python program to solve the "skyline problem"

This is a Leetcode problem - A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the ...
• 2,458
147 views

### A Parallel Processing Template for Divide & Conquer Problems

I’ve written a program for solving a problem using standard single-threaded code. However, it looks like it could be recast as a multi-threaded problem using divide & conquer. Since this is a ...
• 405
657 views

### Finding peak point in an array by using divide and conquer approach

It is to find the maximum element in an array which is first increasing and then decreasing. I've tried to write my idea by using divide and conquer approach. Is there any improvable or missing point? ...
• 393
591 views

### Checking whether given array is sorted by divide-and-conquer

I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately. ...
• 393
4k views

### Closest Pair algorithm implementation in C++

I had been working on the implementation of closest pair algorithm in a 2-D plane. My approach has been that of divide and conquer O(nlogn) : ...
• 121
343 views

### Finding the closest pair of points divide-and-conquer speed improvement

This is a follow up to a previously asked Finding the closest pair of points divide-and-conquer question . The original code changed significantly based on answers from @AJNeufeld therefore I created ...
• 113
6k views

### Finding the closest pair of points divide-and-conquer

Here is my code for the famous "finding the closest pair of points" problem from CLRS book section 33.4 using a divide-and-conquer approach (this code returns the minimum distance between pair of ...
• 113
656 views

### Finding the majority element in a sequence of integers in $O(n \log n)$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in $O(n \log n)$. The majority element is defined as the ...
678 views

### Shortest distance for points in a plane

I was wondering how I can make this code more pythonic. More professonal-looking and more readable. The code runs perfectly fine. ...
1 vote
488 views

### Merge two unsorted array of numbers into sorted array using divide and conquer

I have done an implementation of merging two unsorted array of numbers into single sorted array. I have used the concept of divide an conquer. The code is as follows ...
878 views

### Finding Second Largest Element in an Array

Here's my implementation using divide and conquer in C++. What do you think of this implementation regarding running time ? ...
1 vote
650 views

### Compute the minimum distance between two points in a 2-D plane

I have tried to calculate the minimum distance between the two points in a 2D plane. I have used the divide and conquer strategy to attain the complexity of n logn. ...
• 131
1k views

### Divide and conquer algorithm for max binary gaps

The codility.com free test is as follows: A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary ...
• 329
154 views

### Implementation of binary search

I am new to the divide and conquer paradigm. I wanted to verify that there's nothing wrong with this implementation of binary search. I ran it a few times and it does print the correct result, but I ...
• 329
2k views

### My implementation of Karatsuba Multiplication in C++

I have recently implemented Karatsuba's multiplication algorithm in C++ for my Algorithms course. It is a very sloppy implementation because I ran out of time, yet criticism would be appreciated. I ...
4k views

### 1D Peak Finder Algorithm

I'm reviewing MIT Introduction to Algorithm lectures/exercises and am trying to implement a one dimensional peak finder algorithm. I've got a working copy but it's a bit messy and I've had to put ...
4k views

### Finding closest pair of 2D points, using divide-and-conquer

I'm learning C++ as well as algorithms. Here's my implementation of finding the closest pair problem. I tried to minimize memory by using only iterators. And points are being read from ...
• 241
493 views

### Divide-and-conquer approach for finding the closest pair of points

This is an algorithm for finding the closest pair of points on a 2d plane by dividing the problem by half recursively, as illustrated here: ...
• 1,429
1 vote
283 views

### Random iteration over an array using divide and conquer

I have created a utility class which allows random iteration over an array. The idea is pretty much a divide and conquer approach. ...
• 415
937 views

### Maximum subarray problem solved with divide and conquer also for the all negative element case

Solving the maximum subarray problem with added cases of finding non maximum non contiguous subarray as well. I used divide and conquer approach and tackled the 'all negative' case by keeping a ...
932 views

### Divide and Conquer algorithm for counting inversions

I've written a program that counts the number of inversions using a Divide and Conquer algorithm, written in C++11. ...
• 1,223
1 vote
2k views

### Monge Array - leftmost minimum for each row

This implementation is the result of solving exercise 4-6 "Monge Arrays" from the book Introduction to algorithms. Definition of a Monge Array: An m x n array A of real numbers is a Monge array ...
• 2,974
1k views

### Number to spanish word converter

This converts from a number to a Spanish word for example : 100 => cien 200 => doscientos I used a divide-and-conquer approach: Constants: ...
• 2,974