potter's blog

Check if there is a subsequence with sum divisible by 3.
By potter, history, 3 years ago, In English

PROBLEM

So I came across this problem and I would like to implement and idea that after removing values that are directly divisible by 3 and the pairs that add upto sum (divisible by 3), the rem. ones may have some kind of combination of elements with sum adding upto 3

Example:

arr = [1,1,1,1,1,2,2]

after two operations , pairs gets out [1,2],[1,2] with sum(%3==0)

rem = [1,1,1]

Now, how to know that rem array may have some combinations sum divisible by 3?

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After all your operations, there is a subsequence with sum divisible by 3, if one of these conditions works:

There are at least three elements with the same mod 3

There's at least 1 element mod 3 == 1 and 1 element mod 3 == 2

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The idea is very simple , just replace all the values of the array with a[i]%3 and then count the number of 0s , 1s and 2s and with some small equation u ll end up solving the problem.

→ Reply