Statistics

Problem Statement for "PositiveArray"

Problem Statement

A two-dimensional array of integers is positive if the sum of all elements in each row and each column is strictly greater than zero.

For example, the following array is positive: 

 2  1 -1
-1  2  2

, while the next one is not:

 1  1 -1
-1  2  2

(the sum of the elements in the first column is 0).

You will be given a String[] data, representing a 2-d array. The j-th character of the i-th element of data represents the j-th number in the i-th row of the array. Digits ('0'-'9') denote numbers between 0 and 9, lowercase letters ('a'-'z') denote numbers between 10 and 35, respectively, and uppercase letters ('A'-'Z') denote negative numbers between -1 and -26, respectively. For example, 'a' represents 10, 'c' represents 12, 'A' represents -1 and 'Z' represents -26.

In one move you are allowed to change the signs of all numbers in some row or column (i.e., multiply all numbers in a row or in a column by -1). Return the minimal number of moves you'll need to get a positive array, or -1 if this is impossible.

Definition

Class:
PositiveArray
Method:
countMoves
Parameters:
String[]
Returns:
int
Method signature:
int countMoves(String[] data)
(be sure your method is public)

Constraints

  • data will contain between 1 and 18 elements, inclusive.
  • Each element of data will contain between 1 and 18 characters, inclusive.
  • Each element of data will contain only digits ('0'-'9') or letters ('a'-'z', 'A'-'Z').
  • All elements of data will have the same length.

Examples

  1. {"12"}

    Returns: 0

    The input array is already positive.

  2. {"aB"}

    Returns: 1

    We change signs in the last column and get a positive array.

  3. {"Z2","21"}

    Returns: 2

    We can not succeed with less than 2 moves. One of the possible solutions is to reverse the first row and the last column.

  4. {"10CBA2","3CCCC0","23100B","3AC0AA","BBCBA3","C02100"}

    Returns: 6

  5. {"ABCDEFGHIJKL987654","ABCDEFGHIJKL987654","ABCDEFGHIJKL987654","ABCDEFGHIJKL987654","ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654","ABCDEFGHIJKL987654","ABCDEFGHIJKL987654","ABCDEFGHIJKL987654","ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654","ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654", "ABCDEFGHIJKL987654"}

    Returns: 12

  6. {"88", "3D", "3D"}

    Returns: 2

  7. {"TWVTXZTTWXTWXYWUTW","YXWWVYXZTXUWZUYUZW","UTTYXXVVUXVYYVVYZV","WZYVXUZTUTZYYUTYYX","ZYUYVUWXUTVUVYZWXY","XUVXXVXVVUZXUVWTTZ","WZXTZXXTVUYTZZVWVW","XUYWWWTXTZUVUUXUTW","WYWTUVTWWXZXVVYXZV","WWXXUVXUZVUWUWUVVW","YTXXXUZYTUZXYUZVUT","YWZWXZXUTVZWWTWZYZ","WZYYYTTWYWUXTWZUWU","ZUUVYUTZYXWUUYTZWY","VVVZYWWYTZZYXWVXYW","ZVXZWWZWWWZXXXYTZZ","XWTXZZTVYXVXWTTTYU","TXVZZZUYUZYTXUYUYX"}

    Returns: 18

  8. {"BBB","12B"}

    Returns: -1

  9. {"zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","ZZZZZZZZZZhZZZZZZZ","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz"}

    Returns: -1

  10. {"zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz0zzzzzzz","ZZZZZZZZZZhZZZZZZZ","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","zzzzzzzzzz1zzzzzzz","100000000010000000"}

    Returns: -1

  11. {"z11111111111111111","1zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz0zzzzzzz","ZZZZZZZZZZhZZZZZZZ","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","0zzzzzzzzz1zzzzzzz","A0011E500010000000"}

    Returns: 4

  12. {"000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000","000000000000000000"}

    Returns: -1

  13. {"1A1A1A1A1A1A1A1A1A"}

    Returns: 9

  14. {"1","A","1","A","1","A","1","A","1","A","1","A","1","A","1","A","1","A"}

    Returns: 9

  15. {"wVs76JD4FANeV","J46E7kUldg2po","ZRVgs3T2Z6rG7","omIx0UoeQIt7L","ojxKv3JRhfyoB","E8VaBgng4iog6","dKlx0WeZNEskz","h7nOdybUrIkiL","kqmIK27dNRATK","7o8yrUP9iG79B","NCCbGiMfEmERl","iF3TIGug73luE","3Z0UIfXvKZibV","YUbyKHYjij9ve","lGAzdy62oUpkg","p2tUWBOyCL8KH"}

    Returns: 2

  16. {"0fYXw8XNwijpl"}

    Returns: -1

  17. {"pT8Z","NHG6","07Sh","6hlR","ksiJ","fZJm","S9EV","gcbz","jfVj","Lxtn","05Bs","fLgC","MP8j","S5xo"}

    Returns: 4

  18. {"AEnZ4d0ckwn65G","bJ817RoK3iN2Eh","n5qJhFjLilHQcR","bCcnXMrMzDgkTX","OPh38lzfv1cyjR","jYPDErroYo4OPO","iXSTsJYjRBJG4m","cZVhRW7HuIk07Z","RJmt2GSZYLFw2y","LrlCACWXm617Tu","pAspSwAOgpqldJ","HBs27zBjnR85RK","18xYDuY9c5lgue","JkurMw5GqKUl3F","OjifAoDJMQVFu4"}

    Returns: 5

  19. {"WG0UBvNAZd6","EWLjALlWm1k","jtSHuPjrFeV","MFcCfMxXnBF","QhFvBWHGFSO","ynUlxKmX90N","uDBWiUp6db8","JdHUCpan2JX","Tt5UBC0z2BE","ynDrfedNxHP","woRxtLRWgPM"}

    Returns: 8

  20. {"skmM5UMRRNcsFuarW","4ZMCzKEv3JiruB355","w5vZdze4RyKRWtnAo","Zi6xF5mNZDI2R5y85","ip6UDCVOlwsc2tl6f","2I8kRIE7qoSZAPUWv","EQuHMCvnU4a09bX7T","p2lwQLVH1O6Scsotn","D4467BdoMDHg8uJQC","7Yq70yRDTxZdboriA","eBDuIjcQFDBEdbBwz","F3N7v3sxjEpFyb0Kc","29eoInaPnb79q004Y","nTHe8VAxFJANhhro7","78M8WfXz0KStxOASV","lNLxErfDO6FlCMu5E","5z1jaDeI26NL5IFCe"}

    Returns: 3

  21. {"0WXLDV6PI20T60HPB","FV81NC2YFBTU3ICXB","3U4BA03RNA0FIEBRB","DFK93Y7aNYOKSS8GZ","KC2B1AaLCQ00PHEFF","XaIIC2QSD1UGJK56A","QZG74897RFD58BR2N","aL95UDIW1E4SQ2VZI","FCV4JQLHa77RDPD3H","1C3KEDOSRYSHG4CTR","5U7Ia11FWa39UQF8V","3E7KUBXKHIE4O06HH","SKQY7TROFUYGYSFQT","1C596E2LSWX2ARTOZ","CLQPV6K8I292YERDN","A2C5C683ZDPWB57OM","0LCO5VSEXEGG2FWGT"}

    Returns: 13

  22. {"LCX0MVLaPYHGGII14","P1T4JHHXR01T80KY2","AIY8R0FRKSKF7ZY5R","0HFKMVTLOH5GBH7TE","7OA6YCVAE7VCDQYPY","KICREG94WS366ATUM","19JK6H909D92NaXJU","8KEZaWG8HQ9SAGP55","KVHa3PN8P9J7MBZFB","ZHSLYK5H54UZJ2FWI","M124DDQ6EJD22FQC3","NUCLJK162CJFOJ09R","J7OEOP4YTIQ11NUa0","0LEa642F1WYIUNG85","aNVQMTCYRK18RKV84","19WFPIUE1V1SCAHHI","S63N6U54M2a5V6PEB"}

    Returns: 15

  23. {"6BUHPGUJI0T1YTAV4","aENGN673V703AT1Q9","9K0RZZWXPQIICVY0G","O4aBB7YVANXaDGH5F","1NBAS6RYN57W3M335","UNUGAYO7GFRRWWC1K","B43CFFOEL6KOA2DSB","0010F43aaMBA08XXD","3PHOG5U8STa4YHI39","G8SZ0D6U3F9DYK328","95CMQ159ILVVQOMGD","C0RVMTHDID1395YJW","T8FVQI6L682GLYC0L","3OE7OO0P7T592M4SF","8aHa4V7aSXGTD5UZ5","HTJK5LIT9SHHGVA4P","RXMNZ8QWHWZDYHOFS"}

    Returns: 14

  24. {"A11101A00110A1011","10110AAA01AAA1AAA","000011111A0AA101A","1AAA010000A00000A","A1AA0A0000110A011","A1AAAAAA000A00011","AAA01110A1A101AA1","01011AA0A111A0A1A","1A01AA0000A1A000A","A0A10011A0A1A1000","01001A010A1A01101","001011A001A000010","A100A10001A0A0AAA","1AAA1AAAAA11111AA","A11AAA1A10A10A011","110A110AA0100A110","1A11010001A1110AA"}

    Returns: 12

  25. {"11A100010A0AA0101","1AA111011A01A01AA","A111A1AA0A0AAA01A","1A0A0011110A110A1","A001001A1101AA1AA","A10001A11A000A101","AAA01AA00A010110A","1A01A0A101A111AA0","10A10A11000AA0AAA","0AA01A0A1A1A10101","A00A1A0A001AA00A1","01A01110AAA011A01","00A001A0A11100AA0","0AA001001000A01A0","11110A101111A100A","A1A1AAA001A00A0AA","0111100001AAA11A0"}

    Returns: 11

  26. {"110A00AAAAA10110AA","1A1A0001A1A100A110","AA000A1AA100110A00","10AA111A101110111A","111A001A1011000AA0","AA0110001AAA0AA111","100AAA000AA1A10A1A","AA11A01A11001101A1","111010A1AAAA00A1AA","1011000A10A11111A0","00AA1A11100AA1A01A","1A01A01A00A1001000","AAAA00A11AA0AA1001","AA01AAA1AA00A11110","A011AAA110001A101A","0AA11011A110A10A1A","A0A01A00A11A110101","0001A1A0A10A101A1A"}

    Returns: 13

  27. {"000A0","A0100","00001","A11A1","AA0A1"}

    Returns: 5

  28. {"0A0AA","0001A","01010","A00AA","00111"}

    Returns: 5

  29. {"Z9", "99"}

    Returns: -1

  30. {"ABCDEFGHIJKLMNOPRS", "abcdefghijklmnoprs", "123456789123456789", "888888888888888888", "888AAA888AAA888AAA", "BBB111BBB111BBB111", "CCC222222CCCCCC222", "DDD444DDD444DDD444", "ZZZ999ZZZ999ZZZ999", "zzzZZZzzzZZZzzzZZZ", "CCCaaaCCCaaaCCCaaa", "dddDDDdddDDDdddDDD" }

    Returns: 8

  31. {"BIFTV4OEN9OLR3KUBH", "QXMAGPBFCOSKZP9JXP", "MNWQ1S2GCIZ8VOX7XH", "ZWT6W5XCW6XMFGMAL7", "NNUMZPY0Y7WIPXK409", "ZXPVN62PGY7YOW6GF0", "T8NSC4LGOXM0AW70BR", "6XX322NBA8SK6UCNBH", "D147CKYHXDHLN1OMWI", "TC7C5361LWXO1G7D3U", "U8MHRE2D5VXDRWOJ4A", "HZZDJWD4XATVR9KSDR", "39G2ILRYLVCQHHE32O", "VRVK13FHKYKHIUF2YF", "HIBB090OVLWMREIJ94", "5255R3VUEX4LMI0Q9I", "90OLSDNTDQCF62BPOC", "ZOURVFQPXMV43EJSWC" }

    Returns: 16

  32. {"aa", "9I" }

    Returns: -1

  33. {"lr4lb5lA7FyMDdW9z3", "0Tj8N4k78R2DQKCnXe", "1ShJkbQ2EmbDHeq4Zz", "29Ya9c0O3uN8K5AiVL", "49994icgA7W801mfMf", "I5Jkk756K0U23d6Na6", "0Fvo1palXk9262zy9P", "t7ex9V65Na8B1Kt4dC", "TC2KdVLD0hDz0pKU58", "YO69iqu58BlK3byu7c", "31zpIpHWP5e53S518M", "Ji5ZU5y5EmjY8lN2G4", "0t7WL1lp63maTry4o6", "17u2Wf4Ef0pKI2TJP9", "470g64Vok5j07Se6It", "nI9VA964YOR736y1I4", "4JafPKr40A2GjI1svW", "YwSK5qc4pJ4ldK2iR0" }

    Returns: 3

  34. {"A1B1A1A1A1A1A1A1A1", "1A1A1A1A1A1A1A1A1A", "A1A1A1B1A1A1A1A1A1", "1A1A1A1A1A1A1A1A1A", "A1A1A1A1A1A1A1A1A1", "1A1A1A1B1A1A1B1A1A", "A1A1A1A1B1A1A1A1A1", "1A1A1A1A1A1A1A1A1A", "A1A1A1A1A1A1A1A1A1", "1A1A1A1A1B1A1A1A1A", "A1A1A1A1A1B1A1A1A1", "1A1A1B1A1A1A1A1A1A", "A1A1A1A1A1A1A1A1A1", "1A1A1A1A1A1A1A1A1A", "A1A1A1A1B1A1A1A1A1", "1B1A1A1A1A1A1A1A1A", "A1A1A1A1A1A1A1A1A1", "1A1A1A1A1A1A1A1A1A" }

    Returns: 18

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: