Statistics

Problem Statement for "PotentialArithmeticSequence"

Problem Statement

We have a sequence of N positive integers: a[0] through a[N-1]. You do not know these integers. All you know is the number of trailing zeros in their binary representations. You are given a int[] d with N elements. For each i, d[i] is the number of trailing zeros in the binary representation of a[i].

For example, suppose that a[0]=40. In binary, 40 is 101000 which ends in three zeros. Therefore, d[0] will be 3.

You like arithmetic sequences with difference 1. (That is, sequences in which each element is 1 greater than the previous one. For example, {4,5,6,7}.) For simplicity, we will call these sequences "incrementing sequences".

You would like to count all non-empty contiguous subsequences of the sequence a[0], a[1], ..., a[N-1] that can be incrementing sequences (given the information you have in d).

More precisely: For each pair (i,j) such that 0 <= i <= j <= N-1, we ask the following question: "Given the values d[i] through d[j], is it possible that the values a[i] through a[j] form an incrementing sequence?"

For example, suppose that d = {0,1,0,2,1}. For i=0 and j=3 the answer is positive: it is possible that the values a[0] through a[3] are {1,2,3,4} which is an incrementing sequence. For i=1 and j=4 the answer is negative: there is no incrementing sequence with these numbers of trailing zeros in binary.

Compute and return the number of contiguous subsequences of a[0], a[1], ..., a[N-1] that can be incrementing sequences.

Definition

Class:
PotentialArithmeticSequence
Method:
numberOfSubsequences
Parameters:
int[]
Returns:
int
Method signature:
int numberOfSubsequences(int[] d)
(be sure your method is public)

Constraints

  • n will be between 1 and 50, inclusive.
  • d will contain exactly N elements.
  • Each element of d will be between 0 and 1,000,000,000 (10^9), inclusive.

Examples

  1. {0,1,0,2,0,1,0}

    Returns: 28

    It is possible that the sequence a[0] through a[6] is {1,2,3,4,5,6,7}. All contiguous subsequences of this sequence are incrementing sequences.

  2. {0,0,0,0,0,0,0}

    Returns: 7

  3. {0,0,0,0,1,1,1}

    Returns: 8

  4. {0,100,0,2,0}

    Returns: 11

  5. {1,11,3,0,1,0,1,0,1,0,1,0,3,0,2,0,0,0,0,1,2,3,20}

    Returns: 49

  6. {1000000000,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0}

    Returns: 1275

  7. {0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,999999999}

    Returns: 1275

  8. {0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4}

    Returns: 1275

  9. {0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2}

    Returns: 1275

  10. {1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}

    Returns: 1275

  11. {2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0}

    Returns: 1275

  12. {0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4}

    Returns: 1275

  13. {1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,395813642,3,0,1,0,2,0,1,0,4,0,373805363,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,625420870}

    Returns: 424

  14. {734778810,1,478155934,2,0,1,305408620,4,0,1,0,2,0,1,0,3,0,1,915880938,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1}

    Returns: 573

  15. {0,4,0,1,0,2,358462695,1,0,485730421,0,1,0,2,0,1,0,5,0,1,0,2,0,1,793512937,178703970,0,1,0,2,0,56439854,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6}

    Returns: 351

  16. {1,0,2,0,143183056,0,3,0,1,368457178,2,0,1,0,4,0,1,0,2,0,1,0,521448595,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,688509958,1,0,2,0,1,474627720,4,0,1,0}

    Returns: 330

  17. {1,0,3,0,1,0,2,0,1,328775416,703983279,0,1,0,2,0,1,0,3,0,1,569029877,2,0,1,0,481526113,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,68708759,0,1,0}

    Returns: 435

  18. {0,1,0,1,0,1,0,3,0,1,0,8,0,1,0,7,0,1,0,9,0,1,0,8,0,1,0,3,0,1,0,2,0,1,0,1,0,1,0,1,0,1,0,3,0,1,0,0}

    Returns: 229

  19. {0,1,0,5,0,1,0,8,0,1,0,6,0,1,0,0,0,1,0,4,0,1,0,8,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1}

    Returns: 288

  20. {0,1,0,9,0,1,0,4,0,1,0,5,0,1,0,9,0,1,0,0,0,1,0,3,0,1,0,3,0,1,0,7,0,1,0,8,0,1,0,8,0,1,0,7,0,1,0,6}

    Returns: 237

  21. {0,1,0,2,0,1,0,8,0,1,0,8,0,1,0,8,0,1,0,2,0,1,0,6,0,1,0,4,0,1,0,8,0,1,0,8,0,1,0,9,0,1,0}

    Returns: 274

  22. {0,1,0,2,0,1,0,6,0,1,0,4,0,1,0,6,0,1,0,1,0,1,0,2,0,1,0,0,0,1,0,9,0,1,0,4,0,1,0,7,0}

    Returns: 202

  23. {0,3,1,4,0,2,3,1,0,2,4,1,1,0,1,3,3,1,0,1,0,3,2,2,3,4,3,2,4,4,2,3,3,1,4,3,0,3}

    Returns: 55

  24. {2,4,1,2,0,2,0,3,4,3,1,2,1,2,2,4,4,4,4,3,2,4,4,3,0,3,4,1,2,0,4,3,0,4,4,2,4,4,4,2,0,0,0,3,1,1,1,4,2}

    Returns: 62

  25. {0,1,0,2,4,0,4,3,2,4,2,4,2,3,1,0,4,4,3,1,1,1,3,1,1,2,2}

    Returns: 38

  26. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 50

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

    Returns: 72

  28. {0}

    Returns: 1

  29. {1}

    Returns: 1

  30. {12345}

    Returns: 1

  31. {1000000000}

    Returns: 1

  32. {1000000000,999999999,1000000000,1000000000,999999999,999999999,1000000000,1000000000,1000000000,999999999,999999999,1000000000,1000000000,1000000000,999999999,999999999,999999999,1000000000,1000000000,1000000000,999999999,1000000000,1000000000,1000000000,1000000000}

    Returns: 25

  33. {1,2,1,3,1,2,1,4,1,2,0}

    Returns: 12

  34. {0,2,0,1,2,1,0,2,0,4,0,4,4,4,5,6,5,9,0,12,13,12,14,13,12,13,12,11,10,9,8,7,6,5,4,3,2,1,0}

    Returns: 58

  35. {1, 11, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 3, 0, 2, 0, 0, 0, 0, 1, 2, 3, 20 }

    Returns: 49

  36. {0, 101, 0, 2, 0 }

    Returns: 11

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

    Returns: 14

  38. {0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 999, 0, 1, 0, 2, 0, 1, 0, 100, 0, 1, 0, 2, 0, 1, 0, 4 }

    Returns: 730

  39. {80, 96, 98 }

    Returns: 3

  40. {3, 0, 1, 0, 2, 0, 1 }

    Returns: 28

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

    Returns: 32

  42. {5, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 199999999 }

    Returns: 180

  43. {3, 0, 1, 0, 5 }

    Returns: 14

  44. {33, 0, 2, 0 }

    Returns: 8

  45. {1, 0, 23 }

    Returns: 6

  46. {3, 0, 1, 0, 2 }

    Returns: 15

  47. {101, 0, 1, 0, 2, 0, 1, 0, 10002, 0 }

    Returns: 53

  48. {0, 4, 0, 1, 0, 2, 0, 3 }

    Returns: 30

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

    Returns: 98

  50. {0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 2 }

    Returns: 54

  51. {7, 7, 5, 6, 4, 0, 2, 5, 9, 7, 3, 6, 6, 3, 3, 2, 1, 7, 1, 2, 4, 5, 1, 3, 9, 7, 9, 9, 9, 0, 5, 5, 3, 4, 5, 2, 8, 1, 7, 7, 3, 4, 0, 8, 0, 1, 5, 6, 5, 5 }

    Returns: 61

  52. {0, 1, 0, 3, 0, 1, 0, 14, 0, 1, 0, 7, 0, 1, 0, 23, 0 }

    Returns: 81

  53. {0, 8, 0, 8, 0 }

    Returns: 11

  54. {5, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2 }

    Returns: 414

  55. {13, 1, 0, 0, 1945354, 4220075, 15, 1, 1, 2, 1, 2, 2, 1, 9, 14, 15, 5481180, 1, 2, 7383996, 15, 1, 0, 1, 0, 9, 2, 2, 0, 0, 2, 15, 0, 2, 2, 5137198, 5423434, 2, 9450738, 0, 1, 0, 16, 0, 0, 1, 1, 3037682, 1225355 }

    Returns: 77

  56. {0, 21950, 0, 95103, 0, 5436 }

    Returns: 13

  57. {0, 2, 0, 1, 0, 100 }

    Returns: 21

  58. {1000000000, 0, 1 }

    Returns: 6

  59. {6, 5, 6, 4, 1, 0, 1, 5, 2, 4, 5, 4, 4, 5, 2, 5, 1, 7, 3, 3, 4, 8, 8, 3, 0, 3, 3, 2, 4, 1, 7, 4, 0, 1, 0, 2, 0, 6, 1, 7, 3, 5, 9, 3, 5, 7, 6, 4, 1, 9 }

    Returns: 70

  60. {15, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 }

    Returns: 528

  61. {3, 0, 1, 0, 2, 0, 1, 0, 10000, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0 }

    Returns: 1275

  62. {1000, 0, 1, 100000, 0, 100000, 0, 1, 10000000 }

    Returns: 19

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: