Statistics

Problem Statement for "PowersOfTwo"

Problem Statement

Fox Ciel likes powers of two. She has a bag with some positive powers of two. Note that some powers may occur multiple times in the bag. You are given a long[] powers. Each element of powers is one of the numbers in Ciel's bag.

Ciel likes each non-negative integer that can be written as the sum of some numbers from her bag.

For example, suppose that her bag contains the numbers 2, 4, 4, and 64. In this case, Ciel likes 10 (because 10=2+4+4), 64 (because 64=64), and also 0 (the sum of no numbers). She does not like 1, and she does not like 12 (note that 12=4+4+4 is not valid, as she only has two 4s; 12=4+4+2+2 is also not valid, as she only has one 2).

Return the number of integers Ciel likes.

Definition

Class:
PowersOfTwo
Method:
count
Parameters:
long[]
Returns:
long
Method signature:
long count(long[] powers)
(be sure your method is public)

Constraints

  • powers will contain between 1 and 50 elements, inclusive.
  • Each element of powers is a power of two between 1 and 2^50, inclusive.

Examples

  1. {1,2}

    Returns: 4

    Fox Ciel likes 0, 1, 2 and 3.

  2. {1,1,1,1}

    Returns: 5

    Fox Ciel likes 0, 1, 2, 3 and 4.

  3. {1,2,2,2,4,4,16}

    Returns: 32

  4. {1,32,1,16,32}

    Returns: 18

  5. {1048576,1073741824,549755813888,70368744177664,4398046511104,262144,1048576,2097152,8796093022208, 1048576,1048576,35184372088832,2097152,256,256,256,262144,1048576,1048576,70368744177664,262144,1048576}

    Returns: 18432

  6. {2,4,8,32}

    Returns: 16

  7. {128}

    Returns: 2

  8. {8,524288,281474976710656,16,524288,16,562949953421312,1099511627776,281474976710656,8388608,32,68719476736,16,562949953421312,8388608,140737488355328,1099511627776,16,35184372088832,281474976710656,8,134217728,8388608,68719476736,4,34359738368,8,562949953421312,2147483648,8,562949953421312,562949953421312,16,140737488355328}

    Returns: 1904256

  9. {4,512,34359738368,68719476736,512,35184372088832,4294967296,281474976710656,1048576,2048,64,2048,281474976710656,68719476736,64,4294967296,512,512,512,33554432,512,8589934592,512,2,1048576,4294967296,512,32,34359738368,64,8192,70368744177664,2147483648,1048576,281474976710656,512,4294967296,2048,512}

    Returns: 15654912

  10. {17592186044416,8192,128,8192,8589934592,8192,274877906944,562949953421312,549755813888,128,8589934592,281474976710656,4,65536,16,274877906944,2048,549755813888,8192,549755813888,128,65536,562949953421312,4,524288,4294967296,8589934592,4,134217728,17592186044416,8192,1048576,1073741824,33554432,65536,2199023255552,128}

    Returns: 150405120

  11. {2097152,35184372088832,562949953421312,281474976710656,4294967296,35184372088832,4294967296,17592186044416,2,524288,2147483648,8796093022208,4194304,8388608,2147483648,8,2147483648,17592186044416,274877906944,262144,4294967296,2147483648,4194304,562949953421312,2097152,2097152,536870912,17592186044416,4294967296,16384,4294967296,262144,274877906944,562949953421312,1048576,2147483648,32}

    Returns: 19070976

  12. {2097152,134217728,8589934592,70368744177664,1073741824,2,2097152,1099511627776,32768,64,32,128,70368744177664,2097152,562949953421312,32768,35184372088832,536870912,128,1099511627776,1099511627776,1099511627776,1099511627776,32,536870912,32768,33554432,128,8388608,67108864,8796093022208,8388608,562949953421312,32,35184372088832,33554432,128,2097152,8,1073741824,2097152}

    Returns: 156473856

  13. {2048,274877906944,16384,32768,16384,4194304,1,1,1,1,274877906944,1,16777216,512,268435456,16384,68719476736,2048,8796093022208,32768,8796093022208,8796093022208,1073741824,549755813888,16384,1,64,68719476736,8796093022208,32768,64,8796093022208,16384,549755813888,4398046511104}

    Returns: 6096384

  14. {1099511627776,2048,2048,1099511627776,1073741824,1099511627776,536870912,536870912,65536,2048,1073741824,1099511627776,34359738368,2048,1024,1099511627776,1099511627776,34359738368,64,2048}

    Returns: 7056

  15. {128,8796093022208,128,128,128,128,8796093022208,8796093022208,128}

    Returns: 28

  16. {35184372088832,1024,274877906944,4,2,2199023255552,512,1,1,131072,34359738368,34359738368,32,274877906944,34359738368,140737488355328,8,274877906944,68719476736,2048,34359738368,34359738368,262144,34359738368,2,274877906944}

    Returns: 398848

  17. {140737488355328,2097152,1099511627776,16777216,128,2,524288,16384,8388608,140737488355328,8,4096,2,64,128,1099511627776,512,524288,524288,2097152,4096,8,8,4096,16384,16777216,140737488355328,34359738368,8,4096,131072,17179869184,524288,64,512,137438953472,8,8,4096,4096,4398046511104,131072,4096,274877906944,17179869184,268435456}

    Returns: 1585059840

  18. {562949953421312}

    Returns: 2

  19. {64,2048,268435456,536870912,4194304,64,2048,67108864,67108864,137438953472,8,16,16,262144,70368744177664,536870912,268435456,4398046511104,4194304,4398046511104,2048,4398046511104,274877906944,64,8,64,70368744177664,8589934592,8192,8192,8,8192,2048,8,536870912,262144,262144,137438953472,524288,64,8192}

    Returns: 60011280

  20. {137438953472,137438953472,137438953472}

    Returns: 4

  21. {2097152,131072,2199023255552,2097152,34359738368,8,17179869184,32,8388608,2199023255552,16384,4,70368744177664,64,256,4,512,8,2097152,17179869184,256,256,8388608,2097152,2097152,4294967296,1048576,8388608,2,2097152,2097152,549755813888,2097152,4294967296,67108864,2097152,65536,2097152,2199023255552,64,68719476736,2097152}

    Returns: 167215104

  22. {8388608,131072,32768,4294967296,8192,8192,1048576,4294967296,2,8,131072,8388608,32768,2,1048576,2,32768,131072,2,8192,2,1048576,32768,131072,562949953421312,1048576}

    Returns: 75600

  23. {524288,524288,4,274877906944,16384,131072,16384,524288,16384,4194304,4194304,131072,4,524288,524288,16777216,274877906944,16777216,4194304,4194304}

    Returns: 8424

  24. {562949953421312,131072,274877906944,16777216,281474976710656,8796093022208,17179869184,17179869184,262144,16,8589934592,274877906944,2097152,1125899906842624,262144,1125899906842624,1125899906842624,274877906944,1024,536870912,274877906944,274877906944,8589934592,281474976710656,562949953421312,2097152,16,281474976710656,131072,2147483648,536870912,1125899906842624,2147483648,562949953421312,17179869184,17179869184,2199023255552,16,4096,16,281474976710656,562949953421312,16,17592186044416,8388608,33554432,536870912,16,4096,32}

    Returns: 1666925568

  25. {4,1,536870912,8192,4,140737488355328,4,137438953472,4096,4,32,536870912,32,16777216,32,536870912,4,137438953472,8192,4,32,1073741824,8192}

    Returns: 40320

  26. {2,8796093022208,67108864,67108864,2,274877906944,8796093022208,32,32,8796093022208,256,8796093022208,256,2,67108864,8796093022208,536870912,524288,256,8,536870912,2147483648,1,8,536870912}

    Returns: 221184

  27. {17592186044416,17592186044416,536870912,536870912}

    Returns: 9

  28. {4398046511104,2147483648,8589934592,268435456,16777216,1073741824,8589934592,8589934592,4294967296,17592186044416,1073741824,4096,1073741824,8589934592,34359738368,32768,16384,16384,16777216,512,16384,137438953472,8589934592,1073741824,1073741824,268435456,32768,2199023255552,4096,512,33554432,32,512,16777216,16384,2147483648,137438953472,16384}

    Returns: 8916480

  29. {65536}

    Returns: 2

  30. {67108864,2048,274877906944,562949953421312,549755813888,268435456,1125899906842624,68719476736,4,1073741824,33554432,8,268435456,1073741824,8388608,1024,549755813888,68719476736,67108864,8388608,1024,562949953421312,268435456,549755813888,68719476736,140737488355328,65536,68719476736,8,281474976710656,2048,1099511627776,67108864,281474976710656,562949953421312,140737488355328,67108864,68719476736,4096,549755813888,549755813888,4,256,67108864,1073741824,33554432,67108864,274877906944}

    Returns: 235758600

  31. {34359738368,35184372088832,35184372088832,34359738368,35184372088832,34359738368,35184372088832,34359738368}

    Returns: 25

  32. {17179869184,4398046511104,2147483648,536870912,8589934592,536870912,1099511627776,64,137438953472,4294967296,64,17592186044416,1048576,8192,2147483648,562949953421312,256,64,2147483648,2199023255552,16384,1048576,16384,536870912,2,2147483648,4294967296,128,4194304,512,2199023255552,1073741824,8192,8192,1099511627776,2199023255552,2199023255552,2199023255552,2147483648,4398046511104,8589934592,64,2,2199023255552,1048576,8192,64,4294967296,2199023255552,16}

    Returns: 161533440

  33. {536870912,128,137438953472,65536,4194304,17592186044416,33554432,1,8,1048576,256,17592186044416,262144,536870912,17592186044416,8589934592,17592186044416,262144,256,134217728,512,17592186044416,536870912,65536,134217728,4398046511104,4398046511104,4194304,64,64,1048576,17592186044416,1048576,65536,8,65536,256,1048576,1099511627776,536870912,134217728,134217728,4194304,4398046511104,33554432,17592186044416,4294967296,256,4398046511104,8589934592}

    Returns: 1918700784

  34. {33554432,16777216,67108864,33554432,536870912,1,8388608,34359738368,536870912,33554432,2048,1073741824,16384,68719476736,2199023255552,281474976710656,70368744177664,8388608,8388608,549755813888,16,549755813888,16,2048,16777216,281474976710656,2048,16,68719476736,2048,68719476736,33554432,8388608,68719476736,281474976710656,4294967296,67108864,2048,2048,8192,8192,562949953421312,32,2199023255552,70368744177664,256,1073741824,2199023255552,16777216,33554432}

    Returns: 784546560

  35. {4096,562949953421312,512,274877906944,32768,16,262144,4294967296,4294967296,274877906944,67108864,1,8388608,274877906944,274877906944,65536,274877906944,8192,536870912,4096,4294967296,140737488355328,8192,8388608,140737488355328,274877906944,536870912,137438953472,8192,8,274877906944,536870912,274877906944,274877906944,274877906944,65536,68719476736,32768,67108864,8192,8192,67108864,8192,4096,536870912,4398046511104,562949953421312,8388608,8192,8589934592}

    Returns: 790732800

  36. {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312}

    Returns: 1125899906842624

  37. {1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624,1125899906842624}

    Returns: 51

  38. {1048576, 1073741824, 549755813888, 70368744177664, 4398046511104, 262144, 1048576, 2097152, 8796093022208, 1048576, 1048576, 35184372088832, 2097152, 256, 256, 256, 262144, 1048576, 2048, 1048576, 70368744177664, 262144, 1048576, 1125899906842624, 562949953421312, 281474976710656, 140737488355328, 1024, 512, 2048, 1048576, 70368744177664, 262144, 1048576, 1125899906842624, 562949953421312, 281474976710656, 140737488355328, 4, 8 }

    Returns: 12140544

  39. {1, 32, 1, 16, 32 }

    Returns: 18

  40. {1048576, 1073741824, 549755813888, 70368744177664, 4398046511104, 262144, 1048576, 2097152, 8796093022208, 1048576, 1048576, 35184372088832, 2097152, 256, 256, 256, 262144, 1048576, 1048576, 70368744177664, 262144, 1048576, 1048576, 1073741824, 549755813888, 70368744177664, 4398046511104, 262144, 1048576, 2097152, 8796093022208, 1048576, 1048576, 35184372088832, 2097152, 256, 256, 256, 262144, 1048576, 1048576, 70368744177664, 262144, 1048576, 1, 2, 4, 8, 1, 1 }

    Returns: 8295210

  41. {1, 2, 4, 8, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624 }

    Returns: 1125899906842624

  42. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312 }

    Returns: 1125899906842624

  43. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 1, 2, 4, 8, 16, 32, 64 }

    Returns: 49277

  44. {1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1 }

    Returns: 82

  45. {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16 }

    Returns: 311

  46. {1048576, 1073741824, 549755813888, 70368744177664, 4398046511104, 262144, 1048576, 2097152, 8796093022208, 1048576, 1048576, 35184372088832, 2097152, 256, 256, 256, 262144, 1048576, 1048576, 70368744177664, 262144, 1048576, 1048576, 1073741824, 549755813888, 70368744177664, 4398046511104, 262144, 1048576, 2097152, 8796093022208, 1048576, 1048576, 35184372088832, 2097152, 256, 256, 256, 262144, 1048576, 1048576, 70368744177664, 262144, 1048576, 1048576, 1048576, 1048576 }

    Returns: 519057

  47. {562949953421312, 2, 4, 8, 16, 32 }

    Returns: 64

  48. {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312 }

    Returns: 562949953421312

  49. {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624 }

    Returns: 1125899906842624

  50. {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 2147483648, 4294967296, 8589934592, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184, 17179869184 }

    Returns: 22020096

  51. {1048576, 1073741824, 549755813888, 70368744177664, 4398046511104, 262144, 1048576, 2097152, 8796093022208, 1048576, 1048576, 35184372088832, 2097152, 256, 256, 256, 262144, 1048576, 1048576, 70368744177664, 262144, 1048576, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 8, 1099511627776 }

    Returns: 921600

  52. {1, 1 }

    Returns: 3

  53. {1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624, 1125899906842624 }

    Returns: 51

  54. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648 }

    Returns: 4294967296

  55. {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: 51

  56. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 16, 16, 8, 8, 8, 8, 8, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    Returns: 153

  57. {2, 2, 2 }

    Returns: 4

  58. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888 }

    Returns: 1099511627776

  59. {1, 1, 1, 1, 1, 1, 1, 1, 4, 32, 64, 128, 1024, 128 }

    Returns: 312

  60. {1, 32, 1, 16, 32, 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: 116

  61. {4, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2, 2 }

    Returns: 703687441776640

  62. {1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824, 1073741824 }

    Returns: 22

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: