A program test：
You are given N round clocks.
Every clock has M hands, and these hands can point to positions 1, 2, 3, ..., P (yes, these represent numbers around each face). The clocks are represented by the matrix A consisting of N rows and M columns of integers. The first row represents the hands of the first clock, and so on.
For example, you are given matrix A consisting of five rows and two columns, and P = 4:
A[0][0] = 1 A[0][1] = 2 A[1][0] = 2 A[1][1] = 4 A[2][0] = 4 A[2][1] = 3 A[3][0] = 2 A[3][1] = 3 A[4][0] = 1 A[4][1] = 3
You can rotate the clocks to obtain several clocks that look identical. For example, if you rotate the third, fourth and fifth clocks you can obtain the following clocks:
After rotation, you have four pairs of clocks that look the same: (1, 3), (1, 4), (2, 5) and (3, 4).
type TMatrix = array of array of longint;
Write a function:
int solution(int **A, int N, int M, int P);
int solution(NSMutableArray *A, int P);
int solution(const vector< vector<int> > &A, int P);
class Solution { int solution(int[][] A, int P); }
class Solution { public int solution(int[][] A, int P); }
object Solution { def solution(A: Array[Array[Int]], P: Int): Int }
function solution(A, P);
function solution(A, P)
function solution($A, $P);
function solution(A: TMatrix; N: longint; M: longint; P: longint): longint;
def solution(A, P)
sub solution { my ($A, $P)=@_; my @A=@$A; ... }
def solution(a, p)
Private Function solution ( A As Integer()(), P As Integer ) as Integer
that, given a zero-indexed matrix A consisting of N rows and M columns of integers and integer P, returns the maximal number of pairs of clocks that can look the same after rotation.
For example, given the following array A and P = 4:
A[0][0] = 1 A[0][1] = 2 A[1][0] = 2 A[1][1] = 4 A[2][0] = 4 A[2][1] = 3 A[3][0] = 2 A[3][1] = 3 A[4][0] = 1 A[4][1] = 3
the function should return 4, as explained above.
Assume that:
- N is an integer within the range [1..500];
- M is an integer within the range [1..500];
- P is an integer within the range [1..1,000,000,000];
- each element of matrix A is an integer within the range [1..P];
- the elements of each row of matrix A are all distinct.
Complexity:
- expected worst-case time complexity is O(N*M*log(M)+N*log(N));
- expected worst-case space complexity is O(N*M).
Here is my solution:
1 class Program 2 { 3 static void Main(string[] args) 4 { 5 int[][] Testcase = new int[][] { new int[] { 7, 16, 20, 24 }, new int[] { 5, 14, 18, 22 }, 6 new int[] { 6, 7, 10, 15 }, new int[]{ 6, 7, 10, 15 }, 7 new int[]{ 3, 7, 11, 18 }, new int[]{ 4, 8, 12, 19 } }; 8 //result should be 7 9 Console.WriteLine(new Solution().solution(Testcase, 24));10 }11 }12 13 class Solution14 {15 public int solution(int[][] A, int P)16 {17 int result = 0;18 int hands = A[0].Length;19 20 Dictionary buckets = new Dictionary ();21 buckets.Add (A[0],0);22 23 //fill the buckets24 bool flgFind = false;25 foreach(int[] oneClock in A)26 {27 flgFind = false;28 foreach(int[] bucket in buckets.Keys)29 {30 if (CanbeRotatedToEqual(oneClock, bucket,P) == true)31 {32 buckets[bucket] += 1;33 flgFind = true;34 break;35 }36 }37 if(flgFind == false)38 buckets.Add(oneClock, 1);39 40 }41 42 //calculate the total pairs43 foreach (int k in buckets.Values)44 result += k * (k - 1) / 2;45 46 return result;47 48 }49 50 bool CanbeRotatedToEqual(int[] source, int[] target, int P)51 {52 bool flgJ = false;53 int hands = source.Length;54 for (int i = 0; i < hands; i++)55 {56 int subValue = target[0] - source[i];57 58 flgJ = false;59 for (int j = 0; j < hands; j++)60 {61 int newS = source[(i + j) % hands] + subValue;62 if (newS <= 0)63 newS += P;64 if (newS != target[j])65 {66 flgJ = true;67 break;68 }69 }70 //When flgJ is still false, that means after the source clock rotates subValue steps, 71 //it is identical with the target one.72 if (flgJ == false)73 return true;74 }75 //if this loop end normally, that means the source clock cannot rotate to the target one.76 return false;77 }78 } 2013/8/18: This is not valid version.