wish_me's blog

Tough Problem...
By wish_me, history, 9 years ago, In English

Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.

eg. k=3 arr[1,2,3,-3,-4,1,0,-2,5,4,5]

ans=12 sum from [-2,5,4,5]

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Uhm... What about restrictions? What is the maximum size of A, what is the maximum value of k? Maybe you have a link?

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    maximum size of array 10**3 k<10**2..I got this problem in the interview

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +2 Vote: I do not like it

      Well. If array size is not greater than 1e3 and the time restriction is >1 second(like in the most CF problems), than you can just go for a brute solution:

      //pseudo-code
themaxsum = 0
for i...n
  thesumonseg = 0
  for j = i...n
    thesumonseg = thesumonseg + a[j]
  if thesumonseg % k == 0 && thesumonseg > themaxsum
    themaxsum = thesumonseg
print(themaxsum)

      Assymptotics:O(n * (n + 1) / 2)

      P.S. You can also use prefix solution.

      → Reply
      • »
        »
        »
        »
        9 years ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        you can actually get O(n*k) if you use dp and store the maximum sub segment modulo k.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          can you tell your approach?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            just gonna write the main dp part


            for(int i = 1; i <= n; i++) {
    for(int j = 0; j<k; j++) {
        if(dp[i-1][(j-a[i]+k)%k] !=0) {
            dp[i][j] = dp[i-1][((j-a[i])%k+k)%k] + a[i];
    }
    dp[i][a[i]%k] = max(dp[i][a[i]%k], a[i]);
    ans = max(ans, dp[i][0];
}

            PS: u only actually need 2*k memory, though I am lazy.

            → Reply
        • »
          »
          »
          »
          »
          9 years ago, hide # ^ |
          ← Rev. 3  
          Vote: I like it +5 Vote: I do not like it

          You can actually get O(n) if you store minimum subsegment modulo k.

          We want (sum[r] — sum[l — 1]) % k == 0. That also means that sum[r] % k == sum[l — 1] % k. You just need to remember the minimum sum[x < r] such that it has the same remainder when you divide by k to get the maximum answer. So just pass through the array and see if you have a new answer + update the position sum[x] % k if you need to.

          Edit: this is the O(nlogn) code that works for any k (considering things don't overflow)

          #include <iostream>
#include <map>

typedef long long ll;

int main()
{
	ll n, k, sum = 0;
	std::cin >> n >> k;
	std::map<ll, ll> pref;
	pref[0] = 0;
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	{
		ll temp;
		std::cin >> temp;
		sum += temp;
		if(pref.count((sum % k + k) % k) == 1)
		{
			ans = std::max(ans, sum - pref[(sum % k + k) % k]);
			pref[(sum % k + k) % k] = std::min(pref[(sum % k + k) % k], sum);
		}
		else
		{
			pref[(sum % k + k) % k] = sum;
		}
	}
	std::cout << ans << '\n';
}
          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, hide # ^ |
            ← Rev. 2  
            Vote: I like it 0 Vote: I do not like it

            you are right! The constraints on k made me look for complexity in terms of k..

            though I think I see 2 errors:
            1)it should be max right(for the ans part)? since he is looking for the maximum sum.
            2) you should print ans instead of sum?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, hide # ^ |
               
              Vote: I like it +5 Vote: I do not like it

              Yes you are right my mistake ^^

              → Reply