red_coder's blog

Reducing the complexity……..
By red_coder, 13 years ago, In English

suppose we are given a number 'N' and we want to count all integers >=1 and <=N that are divisible by 'A' or 'B' or 'C' and 'D' or 'E' or 'F' then the code for this would be:

int ans=0;
for(int i=1;i<=N;i++)
  if((i%A==0 || i%B==0 || i%C==0) && (i%D==0 || i%E==0 || i%F==0))
      ans++;

cout<<ans;

the above code would run in O(N) time; but suppose 'N' is too big then is there any faster way to accomplish the above task?????

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

Comments Comments (11)
| Write comment?
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Sauce?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Соус?! О.о

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Педобира, уроженца форчана, удивляет слово соус?

      → Reply
»
13 years ago, # |
  Vote: I like it -13 Vote: I do not like it

please write in english ......

→ Reply
»
13 years ago, # |
  Vote: I like it -13 Vote: I do not like it

use Inclusion-exclusion_principle

Note, A divisble by B and C A divisible by lcm(B,C)

→ Reply
»
13 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Try this with sz=6, but I'm not sure about my code :D.
Complexity: O(22sz) — about 212 operations with sz = 6 :(

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

    can u please tell the logic behind your code. else i would not be able to understand it

    → Reply