Given array of integer, count number of distinct sub array such that it has at most k odd elements and two sub array differ if only when they have at least one member differ.
Example:
{3, 2, 3, 4}, k = 1;
output; 7
[ [3], [2], [4], [3,2], [2,3], [2,3,4],[3,4] ]; Note we did not count [3,2,3] since it has more than k odd elements.
Example 2:
{6, 3, 5, 8}, k = 1;
[ [6], [3], [5], [8] , [6,3], [5,8] ] = 6
We did not count [3,5] as it has > k odd elements
Example 2:
{2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12}
There are these many arrays ;
[2], [2] , [5], [6], [9] , [2], [11], [9], [2], [11], [12]
[2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 9] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [5, 6, 9] , [6, 9, 2] , [9, 2, 11] , [2, 11, 9] , [11, 9, 2] , [2, 11, 12] , [2, 2, 5, 6] , [2, 5, 6, 9] , [5, 6, 9, 2] , [6, 9, 2, 11] , [9, 2, 11, 9] , [2, 11, 9, 2] , [11, 9, 2, 11] , [9, 2, 11, 12] , [2, 2, 5, 6, 9] , [2, 5, 6, 9, 2] , [5, 6, 9, 2, 11] , [6, 9, 2, 11, 9] , [9, 2, 11, 9, 2] , [2, 11, 9, 2, 11] , [11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2] , [2, 5, 6, 9, 2, 11] , [5, 6, 9, 2, 11, 9] , [6, 9, 2, 11, 9, 2] , [9, 2, 11, 9, 2, 11] , [2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9] , [5, 6, 9, 2, 11, 9, 2] , [6, 9, 2, 11, 9, 2, 11] , [9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9] , [2, 5, 6, 9, 2, 11, 9, 2] , [5, 6, 9, 2, 11, 9, 2, 11] , [6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2] , [2, 5, 6, 9, 2, 11, 9, 2, 11] , [5, 6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9, 2, 11, 12]
But only 18 get qualified as there are duplicates like [9, 2, 11] etc.
Qualified arrays are
[2] , [5], [6], [9] , [11], [12] , [2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [6, 9, 2] , [2, 11, 12] , [2, 2, 5, 6]
MY finding so far;
we can use sliding window technique, such that we start counting all sub array of len = 1 to n such that each sub array are different and have at most k odd elements
Here is the code, that i've written for this approach O(n^2)
static int subArraysBrute(int arr[], int k) {
int count = 0;
Set<Integer> set = new HashSet<>();
//Count single length
for (int i = 0; i < arr.length; i++) {
count += set.contains(arr[i]) ? 0 : 1;
set.add(arr[i]);
}
int len = 2;
int odd;
Set<List<Integer>> setArray = new HashSet<>();
while (len < arr.length) {
setArray.clear();
for (int i = 0; i < arr.length - len + 1; i++) {
int j = i + len - 1;
odd = 0;
List<Integer> ar = new ArrayList<>();
for (int x = i; x <= j; x++) {
if (arr[x] % 2 != 0)
odd++;
ar.add(arr[x]);
}
if (!setArray.contains(ar)) {
if (odd <= k) {
count++;
System.out.print(ar + " , ");
}
}
setArray.add(ar);
}
len++;
}
return count;
}
Other findings;
1. We can't sort the array, as they will ruin the subarray property
2. We can't use simple sliding technique as they will mis so many sub arrays ( moving from left to right window) - I've tried this, this fails like any thing;
Probably, in second idea (sliding window), can be improve further such that once we counted sub arrays, we can run one more time and count those sub array which are left out.
solution of approach 2; but still don't know how to do the improvement that i mentioned;
- nitinguptaiit April 20, 2019static int subArrays(int arr[], int k) { int count = 0; Set<Integer> set = new HashSet<>(); //Count single length for (int i = 0; i < arr.length; i++) { count += set.contains(arr[i]) ? 0 : 1; set.add(arr[i]); } int s = 0; int oddCount = 0; int i = 0; for (; i < arr.length; i++) { if (arr[i] % 2 != 0) oddCount++; //count length > 1 if (i - s > 0 && oddCount == k) { count++; } //Slide the window if (oddCount > k) { while (oddCount > k && s < i) { if (arr[s] % 2 != 0) oddCount--; s++; if (i - s > 0 && oddCount == k) { count++; break; } } } } i--; //if left over array has more then 2 element, count them too while (i - s + 1 >= 2) { s++; if (i - s + 1 >= 2) count++; } return count; }