Statistics

Problem Statement for "BinaryPolynomialDivTwo"

Problem Statement

Warning: This problem statement contains superscripts and/or subscripts. It may not display properly outside of the applet.


In this problem we will consider binary polynomials. A binary polynomial can be written in the following form:

P(x) = a[0] * x0 + a[1] * x1 + ... + a[n] * xn

The values a[i] are integer constants (called coefficients). For a binary polynomial we must have a[n] = 1 and each other a[i] must be either 0 or 1. The number n is called the degree of the polynomial.

Several examples:
  • P(x) = 1 * x0 + 0 * x1 + 1 * x2 is a binary polynomial of degree 2.
  • P(x) = 0 * x0 + 1 * x1 + 0 * x2 + 1 * x3 is a binary polynomial of degree 3.
  • P(x) = 1 * x0 is a binary polynomial of degree 0.
  • P(x) = 0 * x0 + 3 * x1 - 1 * x2 is not a binary polynomial, because each coefficient must be a 0 or a 1.
  • P(x) = 0 * x0 is not a valid binary polynomial, because the last of the values a[i] must be 1.
We can evaluate a binary polynomial for the inputs x = 0 and x = 1. In order to do so, we just have to substitute 0 or 1 for x in the above expression, compute the value of the expression and take the remainder it gives when divided by two. For example, if P(x) = 1 * x0 + 0 * x1 + 1 * x2, then P(0) = 1 * 00 + 0 * 01 + 1 * 02 = 1 and P(1) = 1 * 10 + 0 * 11 + 1 * 12 = 0 (modulo 2). Note that in this problem we assume that x0 = 1 for all x. In particular, also 00 = 1.

We call an integer x (where x is 0 or 1) a root of the binary polynomial P if P(x) = 0. You are given a binary polynomial P as the array a of its coefficients. Return the number of roots of that binary polynomial.

Definition

Class:
BinaryPolynomialDivTwo
Method:
countRoots
Parameters:
int[]
Returns:
int
Method signature:
int countRoots(int[] a)
(be sure your method is public)

Constraints

  • The degree of P will be between 0 and 49, inclusive.
  • a will contain exactly n+1 elements, where n is the degree of P.
  • Each element of a will be either 0 (zero) or 1 (one).
  • a[n] will be equal to 1 (one).

Examples

  1. {1, 0, 1}

    Returns: 1

    The example from the problem statement. The only root of this binary polynomial is 1.

  2. {0, 1, 0, 1}

    Returns: 2

    This is the maximum possible answer; both 0 and 1 are roots of this binary polynomial.

  3. {1}

    Returns: 0

    This binary polynomial has no roots - it always evaluates to 1.

  4. {1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1}

    Returns: 0

  5. {1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1}

    Returns: 1

  6. {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1}

    Returns: 0

  7. {1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1}

    Returns: 0

  8. {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1}

    Returns: 2

  9. {0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1}

    Returns: 2

  10. {1, 0, 1, 0, 1}

    Returns: 0

  11. {1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1}

    Returns: 1

  12. {0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1}

    Returns: 1

  13. {1, 1, 1}

    Returns: 0

  14. {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1}

    Returns: 2

  15. {1, 0, 1, 0, 1, 1}

    Returns: 1

  16. {1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1}

    Returns: 0

  17. {0, 1}

    Returns: 1

  18. {0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1}

    Returns: 2

  19. {0, 1, 0, 0, 1, 0, 1, 1, 1, 1}

    Returns: 2

  20. {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1}

    Returns: 1

  21. {0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1}

    Returns: 2

  22. {1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1}

    Returns: 0

  23. {1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1}

    Returns: 0

  24. {0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1}

    Returns: 2

  25. {0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1}

    Returns: 2

  26. {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1}

    Returns: 1

  27. {1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1}

    Returns: 0

  28. {1, 1, 1}

    Returns: 0

  29. {0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1}

    Returns: 1

  30. {1, 1, 0, 0, 1}

    Returns: 0

  31. {1}

    Returns: 0

  32. {0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1}

    Returns: 2

  33. {0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1}

    Returns: 2

  34. {1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1}

    Returns: 1

  35. {1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}

    Returns: 1

  36. {1, 0, 1}

    Returns: 1

  37. {1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1}

    Returns: 0

  38. {1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1}

    Returns: 1

  39. {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}

    Returns: 0

  40. {0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1}

    Returns: 2

  41. {1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1}

    Returns: 1

  42. {0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}

    Returns: 2

  43. {0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1}

    Returns: 1

  44. {0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1}

    Returns: 1

  45. {1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1}

    Returns: 1

  46. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 1

  47. {0, 1}

    Returns: 1

  48. {1, 1}

    Returns: 1

  49. {0, 0, 1}

    Returns: 1

  50. {0, 1, 1}

    Returns: 2

  51. {1, 0, 1}

    Returns: 1

  52. {1, 1, 1}

    Returns: 0

  53. {0, 1 }

    Returns: 1

  54. {0, 1, 0, 1 }

    Returns: 2

  55. {1 }

    Returns: 0

  56. {0, 0, 1 }

    Returns: 1

  57. {0, 1, 1 }

    Returns: 2

  58. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 1

  59. {1, 0, 1 }

    Returns: 1

  60. {1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1 }

    Returns: 0

  61. {1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1 }

    Returns: 1

  62. {1, 0, 1, 1 }

    Returns: 0

  63. {0, 1, 1, 1 }

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: