A counting technique for an apparent intractable problem
The following problem is a variation
of a hacker-rank problem (this one: https://www.hackerrank.com/challenges/picking-numbers).
Given a set of M numbers (M ~= 10,000) and a number N (say N = 5), write an
algorithm to find the largest set amongst the M numbers such that the
difference between any element of that subset is less than N. For example, if
the set of M numbers is {1, 2, 3, 7} and N = 3, then the largest set that
matches the criteria defined would be {1, 2, 3}. Notice that the difference
between any of these numbers is always less than 3 (also, you may assume the
numbers of the set M are within a known range, say M[i] in [1,1000]).
There is a linear
solution to this problem using constant memory, but let’s first analyze the
not-so-optimal solutions. Testing subsets by subsets is clearly intractable
given that the number of subsets for a set of 10,000 elements is a massive number. Another solution
could be to sort the set and then for each element get the largest subset by
traversing the sorted set with 2 nested loops. It might be a feasible approach,
with a pros of constant memory, however the big-O time expectation is still
quite large: NLogN (the sorting) + N^2 (the two nested loops), which yields
O(100,000,000). Certainly doable in a reasonable laptop, but still the moment
that we move the M by one extra zero (M=100,000) it becomes intractable, so I
consider this solution very limited.
The key to solve
this problem in linear time and constant memory is the somewhat casual comment
towards the end of the problem statement: “Also,
you may assume the numbers of the set M are within a known range, say M[i]
in [1,1000].”. That innocent statement unlocks the key to solve the
problem in linear time with constant memory.
Given
that the numbers will all fall within a fixed range, between 1 and 1000, we can
count all the occurrences of these
numbers by using an integer array of length 1000 (call this array S). Then, let’s
think about the core of the problem: find the largest subset of numbers whose
difference between any element is < N. Well, when we look at the array S,
like pick an index within this array say index 4, one possible solution are all
the numbers that fall into positions S[4], S[5], S[6], S[7] and S[8]. All these
numbers differ by less than 5. We can do that for all the indexes in the array
S, and for each index check the partial solution for the N consecutive indexes,
and keep track of the max number of elements. That’s it! This loop only takes
1000*N, and the memory is constant (1000).
Let’s come
up with the final big-O for this algorithm: M (initial parsing adding the
numbers to S) + 1000*N. Since we assume that M >> N, then we have a final
time complexity of O(M).
The image below is an explanation of the code to solve the problem, and the actual code is down below for reference. Counting techniques like this one are commonly used when the problem is constrained to finite and small ranges. Cheers, Marcelo.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
static void Main(String[] args)
{
int n = 1000;
int m = 10000000;
int[] randomNumbers = new int[m];
int minRange = 1;
int maxRange = 10000;
Random rd = new Random();
for (int i = 0; i < randomNumbers.Length; i++)
randomNumbers[i] = rd.Next(minRange, maxRange + 1);
int[] slots = new int[maxRange + 1];
for (int i = 0; i < randomNumbers.Length; i++)
slots[randomNumbers[i]]++;
int maxSetOfNumbers = 0;
int solutionIndex = 0;
for (int i = 0; i < slots.Length - n; i++)
{
int partialSum = 0;
for (int j = 0; j < n; j++)
partialSum += slots[i + j];
if(partialSum > maxSetOfNumbers)
{
maxSetOfNumbers = partialSum;
solutionIndex = i;
}
}
Console.WriteLine("Max set of numbers: {0}", maxSetOfNumbers);
/* debug only
Console.Write("Numbers: ");
for (int i = 0; i < n; i++)
for (int j = 0; j < slots[solutionIndex + i]; j++)
Console.Write("{0} ", solutionIndex + i);
Console.WriteLine();
*/
}
}
Comments
well done, Marcelo! When solving a hackerrank problem I actually didn't even bother to use count sort and used a regular sort, but there is really no need to have 2 nested loops with O(N^2) complexity to find the largest subset - there is only one loop necessary to update start and end indices of a window containing elements satisfying a problem requirement.
Reply DeleteSolution to a hackerrank problem is below (http://ideone.com/SPt4H9):
#include
#include
#include
using namespace std;
int main() {
int n; cin >> n;
vector numbers(n);
for (int i = 0; i < n; ++i) cin >> numbers[i];
sort(numbers.begin(), numbers.end());
int start = 0;
int end = 0;
int length = 0;
int max_length = length;
while (start <= end && end < n) {
if (numbers[end] - numbers[start] <= 1) {
length += 1;
end += 1;
max_length = max(max_length, length);
} else {
length -= 1;
start += 1;
}
}
cout << max_length << endl;
return 0;
}
In order to solve a more generic problem, all we need is to change difference variable value.
Well done...!
Reply Deleteบาคาร่าออนไลน์
จีคลับ
ร้อยไหม
Reply Deleteร้อยไหมปรับรูปหน้า ปรับรูปหน้าที่ไหไนดี ร้อยไหมที่แห่งไหนดี? กังนัมสถานพยาบาลเป็นคําตอบไม่ว่าจะเป็น ร้อยไหมหน้าเรียว เป็นวีไลน์แบบประเทศเกาหลีด้วยไหมก้าง ให้ท่านงามแบบประเทศเกาหลี ลดอายุ หน้าเด็ก ไม่เจ็บ ไม่บอบช้ํา ไม่บวม หน้าเป็นวีเชฟ ลดเหนียง เหนียงกระชับสมปรารถนาร้อยไหม
ร้อยไหมหน้าเรียว
ร้อยไหม วีเชฟ
ร้อยไหมก้างปลา
4 จุดเด่นของการเลือกล่นเกม สล็อต pussy888
Reply Deleteสําหรับผู้ที่ชื่อนถูกใจการเล่นเกมคาสิโนออนไลน์ และก็ดูเกมคสิโนออนไลน์ เกิดเรื่องไม่ดี ไม่สมควรที่จะเข้ามาเล่น จําเป็นต้องกล่าวว่า ในสําหรับบางบุคคลแล้ว การเล่นเกมคาสิโนออนไลน์สล็อต pussy888 บางทีก็อาจจะเป็นอีกหนึ่งตัวช่วย อีกหนึ่งหนทางสําหรับในการทําเงินที่สามารถจะช่วยให้ผู้เล่นเกม สามารถหาเงินเพิ่มให้กับครอบครัวตนเองให้มีชีวิตที่ดียิ่งขึ้นได้ เพราะฉะนั้นเพื่อไม่ให้กําเนิดปัญหาตามมา ผู้เล่นเกมก็เลยจําเป็นต้องเรียนแนวทางการเล่นเกมคาสิโนออนไลน์ให้เข้าใน และก็เลือกเล่นเกมคาสิโนสล็อต pussy888 ที่เหมาะสมกับตนเอง ก็เลยจะช่วยเพิ่มจังหวะสําหรับการทําเงินได้มากขึ้น แล้วก็ถ้าเกิดคุณยงลังเลที่จะเข้ามาเล่นเกมคาสิโนออนไลน์ สามารถเข้ามามอง 4 จุดเด่นของดารเล่นเกมคาสิโนออนไลน์สล็อต pussy888 ที่พวกเราได้จัดแจงไว้ให้ท่านนี้ ค้ําประกันได้เลยว่า มันจะช่วยทําให้ระอุรตกลงใจเข้ามาเล่นกมคาสิโน สล็อต pussy888 ได้ง่ายมากยิ่งกว่าเดิม
4 จุดเด่นที่คุณจําต้องทราบก่อนเข้ามาเล่นเกมสล็อต pussy888
วันนี้พวกเราจะพาคุณไปดู 4 จุดเด่นของการเลือกเข้ามาเล่นเกมสล็อต pussy888 ซึ่งป็นหนึ่งในเกมคาสิโนออนไลน์ยอดฮิต และก็เป็นที่ชอบใจ ของเหล่านักเล่นเกมมากมายก่ายกอง ถ้าหากต้องการรูแล้วว่าจุดเด่นที่ว่านั้น เป็นอย่างไร ตามพวกเราไปดูกันได้เลย
• เกมสล็อต pussy888 เป็นเกมคาสิโนออนไลน์ที่เล่นง่าย โดยเหตุนี้ถ้าเกิดลุกรไม่เคยเล่นเกมคาสิโนออนไลน์มาก่อน หรือยังไม่มีความรู้เกี่ยวกับเกมคาสิโนมาก่อนก็สามารถเล่นเกมสล็อต pussy888ได้ ไม่จําเป็นที่จะต้องมาวิตกกังวลหรือกลุ้มใจ
• คุณสามารถเลือกจ่ายเงินเกิมพันได้เองตามปรารถนา เนื่องจากว่าเกม สล็อต pussy888 ไม่จํากัดเงินสําหรับเพื่อการวางเดิมพัน ทําให้ผู้เล่นเกมสามารถจํากัดวงเงินที่เอามาเล่นเกมคาสิโนออนไลน์นี้ได้
• มีวิธีการสําหรับการเล่นเกม สล็อต pussy888 หลายแบบ ซึ่งจะช่วยเพิ่มจังหวะสําหรับในการทําเงินให้กับผู้เล่นได้อย่างดีเยี่ยม ทําให้มีคนที่พอใจเข้ามาเล่นเกมคาสิโนสล็อต pussy888เพิ่มขึ้นเรื่อยๆ
• ผู้เล่นเกมได้โอกาสทําเงินได้ง่าย ด้วยระบบเกมที่ปรับปรุงขึ้น ทําให้ผู้เล่นเกมมีรายได้ รวมทั้งได้โอกาสที่จะถูกแจ็ตพอเพียงตเกมสล็อต pussy888มากยิ่งกว่าเดิม
เพียงเท่านี้ มั่นใจว่าหลายท่านที่กําลังตกลงใจว่าจะเข้ามาเล่นเกมสล็อต pussy888ดีหรือเปล่า ก็บางครั้งอาจจะตกลงใจแล้ว ซึ่งถ้าเกิดคุณตกลงใจที่จะยามเช้ามาทดลองเล่นเกมคาสิโนออนไลน์นี้มอง อย่าลืมที่จะระวัง รวมทั้งเลือกเล่นเกมสล็อต pussy888อย่างมีสติสัมปชัญญะ คิดให้ถี่ถ้วนก่อนจะจ่ายเงินพนัน หรือเริ่มพนัน ศึกษาเล่าเรียนแนวทางการเล่นเกมให้รู้เรื่อง แล้วก็ให้นานัปการเพิ่มขึ้นเรื่อยๆ สรุปเป็น ผู้เล่นเกมจึงควรเรียนรู้เตรียมความพร้อมเล่นเกมคาสิโนออนไลน์ของตัวคุณเองให้ดีเยี่ยมที่สุด เพื่อความประสบความสําเร็จสําหรับในการเล่นปนคาสิโนออนไลน์ขอทุกคน
pussy888
Post a Comment
[フレーム]