1

Get a number of possible distinct sub-arrays such that they have at most the given number of odd numbers in it.

Example:

arr = [2,1,2,1,3]
m = 2.

Answer:

10

Explanation:

  • Distinct sub arrays with 0 odd numbers = [2]
  • Distinct sub arrays with 1 odd numbers = [2,1], [1], [2,1,2], [1,2] and [3]
  • Distinct sub arrays with 2 odd numbers = [2,1,2,1], [1,2,1], [2,1,3], [1,3]

So a total of 10 possible distinct sub arrays.

Constraints:

The array size can be up to 1000 elements, m can range from 1 to array size.

public static int process(List<Integer> arr, int m) {
    Set<String> set = new LinkedHashSet<>();
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j < arr.size(); j++) {
            int odd = 0;
            StringBuilder sb = new StringBuilder();
            for (int k1 = i; k1 <= j; k1++) {
                if (arr.get(k1) % 2 != 0) {
                    odd++;
                }
                sb.append(arr.get(k1) + " ");
            }
            if (odd <= m) {
                set.add(sb.toString());
            }

        }
    }
    return set.size();
}

This program works for small inputs but as I have 3 for loops it fails for large inputs. What is the correct approach to solve this program?

I have already gone through this post - find number of subarrays with specified number of odd integers but here the questions is not considering about distinct sub arrays.

Hakan Dilek
  • 2,178
  • 2
  • 23
  • 35
learner
  • 6,062
  • 14
  • 79
  • 139

2 Answers2

0

Here's an O(n^2) approach:

  1. lets assume elements are stored in array of size n+1, in places [1....n]
  2. lets modify array accordingly: A[0]=0 and A[i] = A[i-1] + (A[i]%2==1 ? 1 : 0), so now A[i] stores number of odd numbers in range [0...i]
  3. Notice count of odd numbers in some range [i,j] is now the same as A[j]-A[i-1]
  4. Now just check all possible ranges in O(n^2)
  5. For distinct sub arrays we can use a Set/Hash data structure, but we need to store sub array efficiently
  6. most efficient seems to be hashing, we can do polynomial hashing using some base b and modulo m, so that H[0] = 0, H[i] = H[i-1] * b + A[i] % m if a and m are primes which are larger than max input value it should work

pseudo code:

int res = 0;

for(int i=1; i<=n; i++)
 A[i] = A[i-1] + (A[i]%2 == 1);

for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++)
  res+=A[j]-A[i-1] <= m;
Photon
  • 2,717
  • 1
  • 18
  • 22
  • The pseudo code is clear for steps 1 to 4. But I am not able to understand how to get distinct sub-arrays using 5 & 6. Can you please share the code for that also? – learner Jul 13 '20 at 12:39
  • It's same as Rabin-Karp algorithm, if you don't know it you can learn it here: https://cp-algorithms.com/string/rabin-karp.html – Photon Jul 13 '20 at 12:54
  • also do keep in mind that collisions might happen so in that case you can do rabin karp algorithm a few times with different values of `base` and `module` that would reduce collision chance a lot – Photon Jul 13 '20 at 12:55
0

I built a C++ solution for this problem using a Trie. The complexity is O(n²) but it is less expensive in space.

The idea is to build a Trie with all the possibilities, then perform a BFS in the Trie paying attention not to overpass the limit of odd numbers.

#include <bits/stdc++.h>
using namespace std;
#define odd(n) (n % 2 != 0)

struct trie {
    unordered_map<int, trie*> root;
    trie(){ root.clear(); }
    bool contains(int key){ return root.find(key) != root.end();}
    void add(int *arr, int index, int n){
        trie *t = this;
        for(int i = index; i < n; i++){
            if(t->contains(arr[i])){
                t = t->root[arr[i]];
            }
            else{
                t->root[arr[i]] = new trie();
                t = t->root[arr[i]];
            }
        }
    }
    int BFS(int m){
        queue<pair<trie*, int>> q;
        q.push(make_pair(this, 0));
        int ans = 0;
        while(q.size()){
            pair<trie*, int> p = q.front();
            q.pop();
            
            for (auto& it: p.first->root) {
                if(p.second + odd(it.first) <= m) ans++;
                else continue;
                q.push(make_pair(it.second, p.second + odd(it.first)));
            }
        }
        return ans;
    }
};

trie* t;

int main(){
    t = new trie();
    int arr[] = {2,1,2,1,3};
    int n = 5;
    int m = 2;
    
    for(int i = 0; i < n; i++){
        t->add(arr, i, n);
    }
    
    cout<<t->BFS(m)<<endl;

    return 0;
}

OUTPUT: 10.

Daniel
  • 7,357
  • 7
  • 32
  • 84