9
\$\begingroup\$

here I am taking 3 inputs. 1st input will take test cases and the other two input will take starting and ending range. the program is running fine as expected but the limit of this question for compilation is 1 sec, and my code is taking 5.01 sec.

How can I make it more efficient so that I can submit the code?

The challenge was to take number of test cases.

Each test cases show take 2 input (starting and ending range) Eg: 1 4 (i.e 1,2,3,4)

Do the bitwise XOR operation for all of them (i.e 1^2^3^4)

Which when you perform will be equal to 4

Now just check if it is even or odd and print the same.

Here's my code:

from sys import stdin, stdout
t = stdin.readline()
for i in range(int(t)):
    p = 0
    a, b = map(int,stdin.readline().split())
    for x in range(a,b+1):
        p ^= int(x)
    if p % 2 == 0:
        stdout.write(str("Even\n"))
    else:
        stdout.write(str("Odd\n"))

compiling in python 3.6

INPUT:
    4 
    1 4
    2 6
    3 3
    2 3

OUTPUT:
    Even
    Even
    Odd
    Odd

Working perfectly with no issue in code.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Please check that I haven't misrepresented your code, and correct it if I have. \$\endgroup\$ – Toby Speight Jan 29 at 15:01
6
\$\begingroup\$

If you want to make this efficient you should avoid iterating over the range at all.

If you notice that the Xor of four consecutive integers is always even, you can "ignore" them in the final Xor and in the end you only care about the bounds modulo 4, and thus only have to read 4 bits of the input.

A one liner giving you the answer can be written as:

def answer(lo, hi):
  return "Odd" if (((hi ^ lo) >> 1) ^ hi) & 1 else "Even"
\$\endgroup\$
11
\$\begingroup\$

Welcome to CR, nice challenge

A few comments about the code

  • Many unnecessary conversion

    Python is a duck typed language, if it talks like a duck, walks like a duck... it must be a duck!

    This means that

    p ^= int(x)
    

    Here x is already an int, same goes for the str conversion later

  • Use _ variable names for variable you don't use

    for i in range(int(t)):

    Replace the i with _

  • You could return directly

    if p % 2 == 0:
        return "Even"
    else:
        return "Odd"
    

    Instead, you could do which uses a ternary operator

    return "Even" if p % 2 == 0 else "Odd"
    
  • As for the speedup

    I've used this SO link to inspire me, which does a way better job of explaining this then I could ever do

    In short there is a trick to get the XOR'd product of a certain range

    Using the method from the link, I get a massive speedup,

    For these timings: range(1, 1000)

    Bitmagic:  0.023904799999999997
    OP: 2.2717274
    

Code

# https://stackoverflow.com/questions/10670379/find-xor-of-all-numbers-in-a-given-range
def bit_magic(bound):
    magic = [bound, 1, bound + 1, 0]
    return magic[bound % 4]

def bitwise_check(lower_bound, upper_bound):
    p = bit_magic(upper_bound) ^ bit_magic(lower_bound - 1)
    return "Odd" if p & 1 else "Even"

def main():
    n = int(input("Number of testcases: "))
    for _ in range(n):
        lower_bound, upper_bound = map(int, input().split())
        print(bitwise_check(lower_bound, upper_bound))

if __name__ == '__main__':
    main()
\$\endgroup\$
  • 3
    \$\begingroup\$ For the return there is also the option return ["Even", "Odd"][p], but that might be too cryptic. \$\endgroup\$ – Peter Taylor Jan 29 at 17:02
  • 3
    \$\begingroup\$ Is there an objective reason to prefer the ternary to the if/else? I, personally, find the if/else construct more readable than the ternary (which hides the conditional in the middle of the results), and from what I can tell, both ways should result in the same bytecode. \$\endgroup\$ – R.M. Jan 29 at 22:50
  • \$\begingroup\$ @R.M. Agreed - I think if you want to shorten that, the more idiomatic way would be to leave off the else (given that it's redundant with a return in the if) \$\endgroup\$ – sapi Jan 30 at 5:01
  • \$\begingroup\$ @R.M. Not any objective reason, I find it to be more readable but YMMV \$\endgroup\$ – Ludisposed Jan 30 at 11:38
  • \$\begingroup\$ @PeterTaylor normally I would advice against, but since the result can be only 1 or 0 not truthy or falsey, I think it's not super cryptic :) \$\endgroup\$ – Ludisposed Jan 30 at 11:43
11
\$\begingroup\$

If one has a range 1,2,3,4 then only every first bit is interesting for the result; in concreto: whether odd or even. If the number of odd numbers is odd, the result is odd.

def even (lwb, upb):
    n = upb - lwb + 1;
    ones = (n / 2) + (0 if n % 2 == 0 else (upb & 1))
    return ones % 2 == 0

Here lwb (lower bound) and upb (upperbound) inclusive give a range of n numbers (odd even odd even ... or even odd even odd ...). ones is the number of odd.

This means that intelligent domain information can quite reduce the problem.

\$\endgroup\$
  • 2
    \$\begingroup\$ When you use upb & 1, you may consistently replace all …% 2 with … & 1. This also allows to get rid of the conditional: ones = (n / 2) + (n & upb & 1). \$\endgroup\$ – Holger Jan 30 at 13:39
  • \$\begingroup\$ @Holger simplifies indeed. However I did not want to make the code too unreadable (needing an explanation). For instance def odd(lwb, upb) return 1&((n>>1)^(lwb&upb)). But indeed the odd/even test with modulo 2 is ugly looking. \$\endgroup\$ – Joop Eggen Jan 30 at 14:21
10
\$\begingroup\$

The logic is straightforward and easy to follow (albeit with an unnecessary conversion of an int to an int):

p = 0
for x in range(a,b+1):
    p ^= x
return p % 2

However, you could achieve the same more efficiently by noting that we're just counting how many odd numbers are in the range, and reporting whether that count is even or odd. That should suggest a simple O(1) algorithm in place of the O(n) algorithm you're currently using:

def count_odds(lo, hi):
    '''
    Count (modulo 2) how many odd numbers are in inclusive range lo..hi
    >>> count_odds(0, 0)
    0
    >>> count_odds(0, 1)
    1
    >>> count_odds(1, 1)
    1
    >>> count_odds(0, 2)
    1
    >>> count_odds(1, 2)
    1
    >>> count_odds(2, 2)
    0
    >>> count_odds(0, 3)
    2
    >>> count_odds(1, 3)
    2
    >>> count_odds(2, 3)
    1
    >>> count_odds(3, 3)
    1
    '''
    # if lo and hi are both odd, then we must round up,
    # but if either is even, we must round down
    return (hi + 1 - lo + (lo&1)) // 2

if __name__ == '__main__':
    import doctest
    doctest.testmod()

We can then use this function to index the appropriate string result:

if __name__ == '__main__':
    for _ in range(int(input())):
        a,b = map(int, input().split())
        print(["Even","Odd"][count_odds(a,b) & 1])
\$\endgroup\$
  • \$\begingroup\$ I lost you after "don't use p: just p % 2, which" \$\endgroup\$ – Akshansh Shrivastava Jan 29 at 15:20
  • \$\begingroup\$ @Akshansh, I've completely re-written that paragraph to make it clearer. Is that better? \$\endgroup\$ – Toby Speight Jan 29 at 16:25
  • 3
    \$\begingroup\$ Since we're taking %2 or &1, only the low 2 bits of hi and lo matter; if we wanted to make sure this runs fast even with huge inputs (like 1 gigabyte long BigIntegers), we could narrow them before subtracting. But that would complicate the expression and slow down Python for the normal case. \$\endgroup\$ – Peter Cordes Jan 30 at 10:13
  • 1
    \$\begingroup\$ Yes @Peter, I thought of that and decided that clarity was more important for me. :-) \$\endgroup\$ – Toby Speight Jan 30 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.