C++ 1 liner O(1) solution (return n*n/4;) beats 100% with detailed explanation
teaser:\nthe result is as follows\n\nint minOperations(int n) \n{\n\treturn n*n/4;\n}\n\nExplanation (start from an O(n) solution and reduced to an O(1) one):\n
teaser:\nthe result is as follows\n```\nint minOperations(int n) \n{\n\treturn n*n/4;\n}\n```\nExplanation (start from an O(n) solution and reduced to an O(1) one):\ncase 1: 1 (n=average=1)\ncase 2: 1 3 (n=average=2)\ncase 3: 1 3 5 (n=average=3)\ncase 4: 1 3 5 7 (n=average=4)\ncase 5: 1 3 5 7 9 (n=average=5)\nwe count only from 0 to n/2 because each operation can be performed symmetrically on 2 numbers\n```\nint minOperations(int n) \n{\n\tint result=0;\n\tfor(int i=0;i<n/2;i++)\n\t\tresult+=n-2*i-1; //n is the mean (every number should be turned to n)\n\n\treturn result;\n}\n```\n1.We first learn that sum of n from 0~n/2 is n^2/2\n2.We then calculate the sum for 1,3,......,n-1 (2i+1)\nwe can use arithmetic progression formula:N(a1+aN)/2, and N=n/2\n->a1=1,aN=(floor(n/2)-1)x2+1\nso N(a1+aN)/2\n=((1+(floor(n/2)-1)x2+1)floor(n/2))/2=floor(n/2)x2xfloor(n/2)/2=floor(n/2)xfloor(n/2)\nthis can be expressed with nxn/4 in C++\n\nthe result is nxn/2-nxn/4=nxn/4\nhence, result can be reduced to simply {return n * n/4;}
[]