Statistics

Problem Statement for "LinAlg"

Problem Statement

Given an arbitrary number of linear equality equations using an arbitrary (up to 5) number of variables, return the number of distinct possible solutions to the set of equations.

If a set of equations uses the variables (x1, x2, ... xn), a solution is a set of values (r1, r2, ... rn) such that substituting the value ri for the variable xi for all i in all equations results in all the equations evaluating to true equalities.

The number of solutions will always be 0, 1, or infinity. For infinity, return the value 10.

All equations will follow the following grammar:
<EQ> -> <SIDE> "=" <SIDE>
<SIDE> -> integer variable <MORE_VAR_LIST> | integer <MORE_VAR_LIST>
<MORE_VAR_LIST> -> "+" integer variable <MORE_VAR_LIST> | "+" integer <MORE_VAR_LIST> | nil.

Where integer is an integer value, like "23" or "-4" (no space between the negative sign and number) and variable is a single lowercase letter ('a' - 'z'). There can be an arbitrary amount of whitespace between integers, variables, "=" and "+". Leading zeros are allowed in integers, and the integers can range from -10 to 10, inclusive.
For example, an equation might be "03 + 02x = 4y" or "10x + 3y + 2 x = -010".

Definition

Class:
LinAlg
Method:
howMany
Parameters:
String[]
Returns:
int
Method signature:
int howMany(String[] equations)
(be sure your method is public)

Notes

  • If a set of equations contains an equation that cannot possibly be satisfied (like "3 + 4 = 2"), there are no solutions.

Constraints

  • equations will contain between 1 and 50, inclusive, elements.
  • Each element of equations will follow the grammar given above.
  • Each element of equations will have maximum length of 50.
  • No integer in equations will be greater than 10 or less than -10.
  • There will be at least 1 variable in equations.
  • There will be at most 5 variables used in equations.

Examples

  1. {"02x+05y+9x+7z=1x", "10x=5"}

    Returns: 10

    The value of x is fixed at .5, but y and z depend on each other so there are infinitely many solutions.

  2. {"2x+4y=3y", "2x+-04y=2"}

    Returns: 1

    This has exactly one solution, x=.2, y=-.4

  3. {"4a+5b+6c+7d+8e=10", "10=9a+5b+7d+8e", "1=-3a+-2b+-3c+-10d+-5e", "2a+5b=7d+10e", "9=0a+7b+10c+3d+5e"}

    Returns: 1

  4. {"4a+5b+6c+7d+8e=10", "10=9a+5b+7d+8e", "2=-3a+-2b+-3c+-10d+-5e", "2a+5b=7d+9e", "9=0a+7b+10c+3d+5e"}

    Returns: 1

  5. {"4a+5b+6c+7d+8e=10", "10=9a+5b+7d+8e", "2=-3a+-2b+-3c+-10d+-5e", "2a+5b=7d+10e", "9=0a+7b+10c+3d+5e", "9=0a+7b+10c+3d+5e"}

    Returns: 1

  6. {"1x=2", "1x=3"}

    Returns: 0

    Clearly, there is no solution.

  7. {"1 x+1 y=0"}

    Returns: 10

    There are infinitely many solutions. For example (0, 0), (-1, 1), etc...

  8. {"1a + 8b + 1z= 1", "1b + 8c + 1z= 1", "1c + 8d + 1z= 1", "1a+1b+1c+1d+1z=1", "1z+1d=1", "1z=1"}

    Returns: 1

  9. { "1a + 10b = 0", "1b + 10c = 0", "1c + 10d = 0", "1d + 10j = 0", "1j = 10" }

    Returns: 1

  10. {"10a=1", "10b = 1a", "10c = 1b", "10d = 1c", "10j = 1d" }

    Returns: 1

  11. { "10b = 1a", "10c = 1b", "10d = 1c", "10e = 1d", "10a+1e=1" }

    Returns: 1

  12. { "10a+10b+10c+10e=1", "10a=1b", "10b=1c", "10c=1d", "10d=1e" }

    Returns: 1

  13. { "10a+10b+10c+10e=1", "10a=1b", "10b=1c", "10c=1d", "10d=1e", "9a+10b+10c+10e=1" }

    Returns: 0

  14. {"1+1+1+1=4","1x=1x"}

    Returns: 10

  15. {"1x=1", "0x=0", "-1x=-1"}

    Returns: 1

  16. {"-8a+-7b+-7c+2d+0e=-6","2a+3b+-8c+-5d+-5e=2","8a+7b+-3c+-3d+-4e=7","0a+4b+-2c+-6d+-7e=9","6a+1b+-9c+-1d+4e=9"}

    Returns: 1

  17. {"-8a+7b+-9c+5d+0e=-5","1a+-6b+-4c+5d+8e=5","-2a+4b+-3c+6d+1e=3","-9a+0b+4c+-8d+5e=-4","1a+-9b+7c+2d+0e=0"}

    Returns: 1

  18. {"6a+10b+0c+6d+-2e=6","1a+-1b+-4c+-2d+6e=2","7a+-3b+0c+10d+2e=8","5a+-1b+-8c+-8d+5e=1","-7a+-9b+-5c+3d+1e=9"}

    Returns: 1

  19. {"-6a+-3b+2c+-8d+-5e=-7","-5a+4b+-6c+8d+9e=5","0a+6b+-5c+1d+5e=8","0a+10b+-5c+2d+-6e=-6","-3a+3b+5c+0d+-2e=-4"}

    Returns: 1

  20. {"-3a+2b+0c+-2d+-5e=-1","-9a+-3b+-5c+7d+-4e=3","-6a+-8b+-2c+-1d+1e=-7","3a+-1b+2c+0d+9e=2","9a+4b+8c+-3d+-9e=-3"}

    Returns: 1

  21. {"-2a+1b+-4c+-2d+1e=3","0a+4b+1c+7d+-5e=4","1a+2b+5c+-5d+-4e=-5","5a+5b+7c+1d+-6e=8","-7a+8b+2c+-4d+-4e=1"}

    Returns: 1

  22. {"5a+-8b+-8c+0d+-9e=6","9a+8b+-1c+9d+6e=6","-9a+7b+0c+5d+-9e=-2","-1a+4b+0c+-5d+2e=3","5a+9b+0c+4d+8e=-6"}

    Returns: 1

  23. {"-9a+4b+2c+7d+5e=8","5a+4b+10c+-1d+-4e=8","6a+8b+2c+1d+1e=10","7a+-8b+-5c+1d+4e=-8","0a+-9b+10c+4d+0e=-8"}

    Returns: 1

  24. {"-3a+-2b+1c+0d+-8e=-4","5a+7b+2c+-1d+-8e=5","-6a+-9b+5c+-2d+-2e=-6","8a+6b+-9c+7d+-4e=-1","-7a+-7b+2c+-5d+-1e=-2"}

    Returns: 1

  25. {"9a+-4b+4c+3d+-5e=3","-3a+-7b+6c+0d+-7e=-9","1a+8b+0c+0d+-8e=3","10a+-3b+4c+7d+8e=1","4a+7b+3c+3d+5e=-9"}

    Returns: 1

  26. {"4a+4b+10c+10d+8e=-5","0a+-9b+1c+-7d+-5e=-2","-8a+-4b+-2c+0d+0e=3","9a+6b+10c+7d+7e=7","-2a+5b+4c+-1d+0e=-1"}

    Returns: 1

  27. {"-7a+-9b+-5c+-8d+-7e=-2","4a+2b+6c+-6d+0e=-4","-9a+-3b+3c+7d+4e=8","-8a+3b+-9c+0d+-8e=-1","-2a+7b+9c+0d+-4e=-2"}

    Returns: 1

  28. {"-7a+-5b+-7c+-1d+4e=-9","-1a+8b+-3c+0d+0e=7","-7a+0b+-3c+-1d+0e=-8","7a+-3b+-3c+-3d+0e=-7","0a+7b+4c+0d+-4e=-8"}

    Returns: 1

  29. {"-3a+-9b+-6c+4d+-2e=7","-9a+-3b+0c+4d+2e=-4","5a+1b+8c+10d+5e=4","0a+7b+1c+1d+2e=-6","-4a+-4b+-2c+0d+9e=9"}

    Returns: 1

  30. {"0a+-1b+8c+-9d+1e=-8","10a+6b+7c+-9d+6e=-6","8a+-7b+-9c+-1d+5e=1","10a+-7b+0c+0d+-2e=-6","-6a+-8b+-3c+-5d+10e=9"}

    Returns: 1

  31. {"-6a+0b+0c+-1d+6e=-1","6a+4b+-2c+7d+1e=-1","-3a+1b+-9c+-2d+6e=-7","6a+8b+-7c+-7d+0e=-5","-2a+9b+0c+0d+2e=9"}

    Returns: 1

  32. {"4a+4b+-1c+8d+7e=1","-3a+-9b+-9c+-6d+5e=5","-2a+-7b+0c+-9d+4e=10","-3a+-5b+-7c+2d+8e=10","3a+7b+-9c+7d+-7e=2"}

    Returns: 1

  33. {"8a+-7b+-4c+4d+0e=9","-2a+-8b+-5c+-2d+0e=-2","0a+-8b+-8c+7d+-8e=-9","4a+-3b+7c+4d+3e=-6","0a+5b+-8c+-1d+1e=-6"}

    Returns: 1

  34. {"10a+0b+-6c+7d+0e=0","-3a+8b+-1c+9d+-5e=-3","-9a+-7b+-6c+4d+0e=7","6a+4b+6c+-4d+9e=7","0a+-1b+-2c+-3d+2e=0"}

    Returns: 1

  35. {"-4a+9b+0c+-5d+10e=7","-6a+7b+2c+0d+-3e=-4","-5a+2b+0c+4d+0e=-7","0a+-7b+3c+4d+6e=-5","-6a+-7b+3c+7d+1e=6"}

    Returns: 1

  36. {"6a+-1b+-4c+-2d+-6e=6","-8a+3b+-7c+5d+-4e=10","10a+-4b+0c+-9d+-4e=-6","4a+-4b+-5c+6d+10e=-5","3a+-5b+-9c+4d+0e=3"}

    Returns: 1

  37. {"8a+10b+-4c+7d+-3e=6","3a+8b+2c+2d+1e=5","5a+-9b+8c+8d+-1e=-1","-4a+-9b+-9c+0d+6e=-7","0a+-5b+-9c+8d+7e=5"}

    Returns: 1

  38. {"8a+3b+9c+-4d+-3e=2","-4a+9b+0c+7d+-5e=-1","6a+9b+-8c+5d+10e=-6","6a+-4b+-2c+-4d+4e=4","-1a+7b+4c+8d+-8e=-2"}

    Returns: 1

  39. {"0a+0b+2c+5d+-1e=5","0a+-9b+-3c+10d+4e=-4","1a+2b+-9c+9d+0e=-9","-2a+3b+2c+-6d+-4e=4","5a+-6b+-9c+5d+-4e=2"}

    Returns: 1

  40. {"-2a+6b+5c+-9d+6e=-4","-8a+-3b+-9c+8d+4e=-3","0a+0b+10c+1d+0e=6","-7a+2b+6c+10d+0e=-3","7a+-5b+3c+5d+-9e=-7"}

    Returns: 1

  41. {"-6a+6b+-7c+0d+-1e=7","0a+-9b+-1c+5d+7e=-2","5a+0b+0c+5d+0e=0","8a+9b+-7c+0d+2e=-8","10a+8b+-1c+2d+2e=-3"}

    Returns: 1

  42. {"-7a+-6b+4c+-7d+5e=-5","-6a+-7b+-7c+-6d+8e=8","-8a+3b+10c+-5d+5e=3","-6a+-9b+4c+6d+3e=1","8a+-9b+8c+0d+2e=0"}

    Returns: 1

  43. {"3a+6b+0c+8d+3e=-4","2a+3b+-5c+4d+-2e=4","-2a+-5b+-5c+-6d+1e=5","-6a+-1b+-2c+5d+1e=-3","6a+3b+8c+5d+3e=4"}

    Returns: 1

  44. {"-7a+3b+-4c+2d+-1e=8","-5a+0b+7c+-4d+6e=-6","5a+5b+6c+-8d+7e=8","-6a+0b+5c+5d+2e=-9","9a+7b+8c+2d+0e=0"}

    Returns: 1

  45. {"-8a+-3b+10c+-1d+-1e=2","10a+6b+0c+1d+9e=-5","-9a+-9b+5c+6d+10e=-9","10a+6b+3c+6d+-9e=-5","1a+-1b+4c+1d+9e=4"}

    Returns: 1

  46. {"0a+9b+3c+-2d+-9e=-4","-4a+7b+6c+3d+9e=0","9a+7b+-5c+-6d+-3e=-3","-9a+9b+8c+-9d+0e=-4","-2a+-7b+-6c+2d+7e=0"}

    Returns: 1

  47. {"2a+-2b+-3c+-1d+1e=0","-1a+-7b+6c+9d+1e=5","0a+-2b+-5c+8d+10e=-9","0a+-1b+0c+9d+0e=4","9a+8b+-3c+9d+-4e=1"}

    Returns: 1

  48. {"10a+0b+3c+-9d+6e=-8","-1a+9b+5c+-6d+-4e=0","-6a+0b+-6c+4d+3e=4","-8a+-5b+10c+-7d+-8e=6","6a+-2b+-6c+8d+10e=9"}

    Returns: 1

  49. {"-5a+10b+7c+8d+-9e=-1","-1a+8b+8c+-8d+-6e=3","-9a+6b+4c+9d+-5e=-7","2a+6b+-3c+-7d+2e=0","5a+-1b+9c+0d+5e=-4"}

    Returns: 1

  50. {"-9a+-7b+7c+6d+0e=8","3a+9b+3c+-2d+9e=-7","5a+0b+0c+-8d+-3e=8","4a+6b+4c+0d+0e=-5","0a+-1b+5c+6d+6e=2"}

    Returns: 1

  51. {"-6a+-6b+7c+-5d+5e=-5","9a+6b+2c+-6d+8e=9","7a+-8b+-5c+10d+5e=-4","-2a+-9b+-4c+7d+-2e=-3","8a+-8b+1c+-8d+9e=-8"}

    Returns: 1

  52. {"-9a+9b+-7c+-4d+4e=-4","7a+5b+-9c+6d+6e=-8","3a+-5b+-8c+10d+9e=2","7a+10b+8c+3d+5e=-5","6a+7b+-9c+-4d+3e=-1"}

    Returns: 1

  53. {"3a+3b+4c+-5d+-4e=-8","-2a+9b+7c+5d+0e=4","5a+10b+3c+5d+5e=-6","10a+8b+4c+8d+0e=-9","3a+0b+-1c+0d+-3e=5"}

    Returns: 1

  54. {"2a+-7b+-1c+-7d+10e=10","-8a+-5b+-8c+5d+1e=5","0a+-3b+-1c+-7d+-1e=10","9a+-4b+3c+1d+-4e=6","8a+10b+4c+0d+-5e=-5"}

    Returns: 1

  55. {"-2a+-2b+-5c+0d+-4e=7","0a+-1b+-5c+-7d+0e=8","7a+6b+9c+5d+1e=-8","0a+-2b+5c+9d+-7e=-4","4a+-9b+5c+-1d+7e=1"}

    Returns: 1

  56. {"0a+4b+-3c+2d+-2e=7","-6a+-9b+-5c+4d+6e=6","10a+8b+-5c+-6d+6e=10","-3a+-8b+5c+-9d+10e=-6","-2a+7b+-9c+6d+2e=2"}

    Returns: 1

  57. {"-8a+-5b+6c+-6d+-1e=5","4a+-9b+0c+-3d+-2e=-7","-5a+-8b+1c+8d+1e=-7","4a+9b+7c+6d+-2e=-8","10a+4b+-3c+8d+-9e=8"}

    Returns: 1

  58. {"6a+-6b+-5c+0d+0e=5","10a+-8b+-1c+-2d+-5e=-9","10a+3b+-8c+3d+-6e=10","-7a+-7b+5c+0d+-1e=10","-5a+9b+0c+4d+-2e=-1"}

    Returns: 1

  59. {"-9a+4b+-1c+4d+10e=9","3a+-4b+0c+1d+-7e=0","4a+-7b+-4c+10d+-6e=-5","-3a+6b+4c+-4d+8e=8","0a+-6b+2c+-6d+-7e=6"}

    Returns: 1

  60. {"10a+3b+3c+0d+0e=2","-2a+-3b+0c+-7d+-9e=0","-2a+10b+2c+0d+-2e=-1","-2a+6b+10c+-2d+-6e=8","5a+3b+3c+0d+-9e=-3"}

    Returns: 1

  61. {"5a+-4b+3c+4d+9e=8","0a+9b+-5c+-5d+5e=-9","5a+-1b+8c+2d+-8e=6","5a+0b+8c+-5d+0e=-3","-7a+-1b+10c+-7d+7e=4"}

    Returns: 1

  62. {"0a+-5b+-2c+-3d+-6e=0","2a+1b+10c+5d+-5e=-4","0a+7b+-9c+10d+1e=-5","10a+2b+10c+-7d+-1e=-4","-7a+-3b+9c+0d+0e=8"}

    Returns: 1

  63. {"3a+-9b+5c+-8d+-5e=-7","6a+6b+4c+-5d+2e=1","5a+-8b+-8c+-7d+-1e=6","-2a+-9b+8c+8d+6e=9","-3a+-1b+0c+0d+10e=1"}

    Returns: 1

  64. {"9a+10b+4c+0d+-9e=7","8a+0b+-4c+-4d+-5e=9","-3a+-7b+0c+-7d+-3e=0","9a+4b+4c+5d+4e=-9","3a+-9b+-7c+2d+1e=-3"}

    Returns: 1

  65. {"-7a+-4b+6c+6d+5e=10","-8a+-4b+-8c+-7d+0e=-1","1a+-1b+9c+-2d+8e=-4","-6a+-3b+9c+2d+7e=9","9a+0b+4c+1d+-8e=0"}

    Returns: 1

  66. {"1x=1y","1y=1z","1x=1z","1x+1y=1y+1z"}

    Returns: 10

  67. {"1x=1y","1y=1z","1x=1z","1x+1y=1y+1z","1x+1y=2"}

    Returns: 1

  68. {"1x=1y","1y=1z","1x=1z","1x+1y=1y+1z","1x+1y=1z"}

    Returns: 1

  69. {"8a+-6b+0c+0d+0e=10","9a+9b+6c+4d+-7e=7","0a+5b+-1c+-1d+-5e=-4","0a+0b+-3c+-6d+7e=3","-8a+0b+0c+0d+2e=2","-7a+-1b+4c+-4d+4e=3"}

    Returns: 0

  70. {"1x+1z=1","1z=0","1x=0"}

    Returns: 0

  71. { "2x+3y=5", "3x+2y=5", "5x+5y=10" }

    Returns: 1

  72. { "2x+3y=2", "4x+6y=4" }

    Returns: 10

  73. { "1a + 1b = 1", "1a + 2b = 1" }

    Returns: 1

  74. { "2x + -04y = 2 ", "2x + 4y = 3y " }

    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: