for(int i=1; i<=a;i++){
for(int j=1;j<=b;j++){
if((i+j)%2 == 0){
count++;}}}
Can anyone reduce the Time complexity of this problem? I am finding great difficulty in doing it.
Asked
Active
Viewed 192 times
0
Chandrachud Pati
- 425
- 1
- 5
- 12
-
1How many odd numbers in `[1, a]` and `[1, b]`? How many even numbers? – Jarod42 Dec 10 '20 at 20:57
-
1Hint, `even + even == even`, `odd + odd = even`, `even + odd == odd` – NathanOliver Dec 10 '20 at 21:00
-
No this isn't the exact problem. – Chandrachud Pati Dec 10 '20 at 21:00
-
Well if you described what the problem is, we might be able to give you a better algorithm to do it. – NathanOliver Dec 10 '20 at 21:02
-
Two x and y, to find the even pair sum such that 1≤a≤x, 1≤b≤y and a+b is even. – Chandrachud Pati Dec 10 '20 at 21:03
-
Our hints give `O(1)` complexity instead of your `O(n²)`. – Jarod42 Dec 10 '20 at 21:04
-
@Jarod42 How did you do $O(n^2)$ – Kostas Dec 10 '20 at 21:18
-
@Kostas: it was on my (French) azerty keyboard. – Jarod42 Dec 10 '20 at 21:26
-
`int count = a/2 * b/2 + (a+1)/2 * (b+1)/2`. Apparently you can't easily simplify things when floor division is involved. My regards to the compiler. – Kostas Dec 10 '20 at 21:30
-
@Kostas or just `int count = (a*b)/2.` – Erwan Dec 10 '20 at 21:39
-
1You appear to have asked the same question in [python](https://stackoverflow.com/questions/65212883). What you're asking about is actually an algorithm question, and the answer is going to be the same in every programming language. Perhaps you want to add the [tag:algorithm] tag? – cigien Dec 11 '20 at 00:44