My solution of this task is (i assume) time complexity O(N^2). Obviously my code is not handling well large arrays. How could I make this more efficient? What am I missing? Could you guys recommend some material that could help me understand how to write more efficient code in C? Thanks!
Task:
A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] A[1] ... A[P − 1]) − (A[P] A[P 1] ... A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
For example, consider array A such that:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3We can split this tape in four places:
P = 1, difference = |3 − 10| = 7 P = 2, difference = |4 − 9| = 5 P = 3, difference = |6 − 7| = 1 P = 4, difference = |10 − 3| = 7Write a function:
int solution(int A[], int N);that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.
For example, given:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3the function should return 1, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−1,000..1,000].
My solution:
#include <stdint.h>
#include <stdlib.h>
int solution(int A[], int N) {
uint32_t p = 1, i=0;
int64_t lowestSum = 0, sum1 = 0, sum2 = 0, sum = 0;
{
// iterate over all possible values of P
for(p=1; p<N; p )
{
sum1 = 0;
sum2 = 0;
for(i=0; i<N; i )
{
if(i<p)
{
sum1 = A[i];
}
else
{
sum2 = A[i];
}
}
sum = abs(sum1 - sum2);
//if this is the first iteration,
//initialize the lowest sum with current sum
if(p==1)
{
lowestSum = sum;
}
else if(lowestSum > sum)
{
lowestSum = sum;
}
}
}
return lowestSum;
}
CodePudding user response：
The data constraints show that the maximum sum of the inputs is 100000 * 1000 = 100000000 which can fit a 32-bit int.
I suggest that if the data is coming from a stream, all you need is to store the running sum of the values in a first pass, and figure out the answer in a second pass.
This is O(N).
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
int n = 0;
int sum = 0;
scanf("%d", &n);
int *left = malloc(n * sizeof *left);
for(int i = 0; i < n; i ) {
int val;
scanf("%d", &val);
sum = val;
left[i] = sum;
}
int mindiff = INT_MAX;
for(int i = 0; i < n; i ) {
int right = sum - left[i];
int diff = abs(left[i] - right);
if(diff < mindiff) {
mindiff = diff;
}
}
printf("mindiff = %d\n", mindiff);
free(left);
return 0;
}
For the specified input
5
3 1 2 4 3
The output is
mindiff = 1
I realise the program is devoid of any error checking, which isn't great, but it does show the algorithm.
CodePudding user response：
Based on advices provided by Weather Vane and Jonathan Leffler I was able to comeup with this solution, which was given 100% result. The lesson learned is to simply try avoid O(N^2) solutions at any cost. I wish I could train my mind to see these solutions (faster).
#include <stdint.h>
#include <stdlib.h>
int solution(int A[], int N) {
int64_t LeftRight[N], sum = 0;
int64_t lowest_diff = 0, diff = 0;
uint32_t i = 0;
for(i=0; i<N; i )
{
sum = A[i];
LeftRight[i] = sum;
}
sum = 0;
i = N - 1;
while(i > 0)
{
sum = A[i];
diff = abs(LeftRight[i-1]-sum);
//is this first elemnt on the right?
if(i == (N-1))
{
lowest_diff = diff;
}
else if(lowest_diff > diff)
{
lowest_diff = diff;
}
i--;
}
return lowest_diff;
}
CodePudding user response：
Here is some fairly fancy code I developed, but the core algorithm use O(1) space and O(N) time for the analysis, making just 2 passes over the data.
This program takes an optional -v argument to print a verbose analysis of its working. It uses my normal error handling code which is available in my SOQ (Stack Overflow Questions) repository on GitHub as files stderr.c and stderr.h in the src/libsoq sub-directory. I find that it makes error handling much easier, so I'm more inclined to actually do the necessary error checking. It checks that the input meets the conditions and reports errors (and bails out) if the data is invalid. It adapts the detailed layout of the verbose data to keep columns aligned.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "stderr.h"
static const char optstr[] = "vh";
static const char usestr[] = "[-vh]";
static const char hlpstr[] =
" -h Print this help message and exit\n"
" -v Print details of calculation as it is done\n"
;
static int solution(int A[], int N);
static int vflag = 0;
static int n_width = 0;
static int s_width = 0;
int main(int argc, char **argv)
{
err_setarg0(argv[0]);
int opt;
while ((opt = getopt(argc, argv, optstr)) != -1)
{
switch (opt)
{
case 'v':
vflag = 1;
break;
case 'h':
err_help(usestr, hlpstr);
/*NOTREACHED*/
default:
err_usage(usestr);
/*NOTREACHED*/
}
}
if (optind != argc)
err_usage(usestr);
int N;
if (scanf("%d", &N) != 1)
err_error("failed to read array size\n");
if (N < 2 || N > 100000)
err_error("array size %d out of range 2..100,000\n", N);
/* VLA - but size was checked and won't overflow stack */
int array[N];
for (int i = 0; i < N; i )
{
if (scanf("%d", &array[i]) != 1)
err_error("failed to read element %d of array\n", i);
if (array[i] < -1000 || array[i] > 1000)
err_error("element %d (%d) is out of range -1000.. 1000\n", i, array[i]);
}
n_width = snprintf(0, 0, "%d", N - 1);
s_width = snprintf(0, 0, "%d", (N - 1) * -1000);
int result = solution(array, N);
printf("result: %d\n", result);
return 0;
}
static inline int abs_diff(int a, int b)
{
return abs(a - b);
}
static int solution(int A[], int N)
{
int total = 0;
/* First pass over array - O(N) */
for (int i = 0; i < N; i )
total = A[i];
if (vflag)
printf("N = %d; total = %d\n", N, total);
/* Second pass over array - O(N) */
int lhs = A[0];
int min_gap = abs_diff(lhs, total - lhs);
if (vflag)
{
printf("A[%*d] = ]: lhs = %*d, rhs = %*d, |lhs - rhs| = %*d ** minimum so far\n",
n_width, 0, A[0], s_width, lhs, s_width, total - lhs,
s_width, abs_diff(lhs, total - lhs));
}
for (int i = 1; i < N; i )
{
lhs = A[i];
int diff = abs_diff(lhs, total - lhs);
if (vflag)
{
const char *marker = (diff < min_gap) ? " ** minimum so far" : "";
printf("A[%*d] = ]: lhs = %*d, rhs = %*d, |lhs - rhs| = %*d%s\n",
n_width, i, A[i], s_width, lhs, s_width, total - lhs,
s_width, abs_diff(lhs, total - lhs), marker);
}
if (diff < min_gap)
min_gap = diff;
}
return min_gap;
}
For the sample data in the question, the verbose output is:
N = 5; total = 13
A[0] = 3: lhs = 3, rhs = 10, |lhs - rhs| = 7 ** minimum so far
A[1] = 1: lhs = 4, rhs = 9, |lhs - rhs| = 5 ** minimum so far
A[2] = 2: lhs = 6, rhs = 7, |lhs - rhs| = 1 ** minimum so far
A[3] = 4: lhs = 10, rhs = 3, |lhs - rhs| = 7
A[4] = 3: lhs = 13, rhs = 0, |lhs - rhs| = 13
result: 1
Note that there is one more line of output than the analysis in the question shows.
For a 20-line random input, I got:
N = 20; total = 973
A[ 0] = -360: lhs = -360, rhs = 1333, |lhs - rhs| = 1693 ** minimum so far
A[ 1] = -675: lhs = -1035, rhs = 2008, |lhs - rhs| = 3043
A[ 2] = 245: lhs = -790, rhs = 1763, |lhs - rhs| = 2553
A[ 3] = 47: lhs = -743, rhs = 1716, |lhs - rhs| = 2459
A[ 4] = -100: lhs = -843, rhs = 1816, |lhs - rhs| = 2659
A[ 5] = 987: lhs = 144, rhs = 829, |lhs - rhs| = 685 ** minimum so far
A[ 6] = 16: lhs = 160, rhs = 813, |lhs - rhs| = 653 ** minimum so far
A[ 7] = -146: lhs = 14, rhs = 959, |lhs - rhs| = 945
A[ 8] = 126: lhs = 140, rhs = 833, |lhs - rhs| = 693
A[ 9] = -541: lhs = -401, rhs = 1374, |lhs - rhs| = 1775
A[10] = -116: lhs = -517, rhs = 1490, |lhs - rhs| = 2007
A[11] = 842: lhs = 325, rhs = 648, |lhs - rhs| = 323 ** minimum so far
A[12] = -769: lhs = -444, rhs = 1417, |lhs - rhs| = 1861
A[13] = -361: lhs = -805, rhs = 1778, |lhs - rhs| = 2583
A[14] = 295: lhs = -510, rhs = 1483, |lhs - rhs| = 1993
A[15] = -471: lhs = -981, rhs = 1954, |lhs - rhs| = 2935
A[16] = 398: lhs = -583, rhs = 1556, |lhs - rhs| = 2139
A[17] = 932: lhs = 349, rhs = 624, |lhs - rhs| = 275 ** minimum so far
A[18] = 270: lhs = 619, rhs = 354, |lhs - rhs| = 265 ** minimum so far
A[19] = 354: lhs = 973, rhs = 0, |lhs - rhs| = 973
result: 265
For a full 100,000 line input, the output started and ended like this:
N = 100000; total = -53534
A[ 0] = -301: lhs = -301, rhs = -53233, |lhs - rhs| = 52932 ** minimum so far
A[ 1] = 338: lhs = 37, rhs = -53571, |lhs - rhs| = 53608
A[ 2] = -35: lhs = 2, rhs = -53536, |lhs - rhs| = 53538
A[ 3] = 243: lhs = 245, rhs = -53779, |lhs - rhs| = 54024
A[ 4] = -537: lhs = -292, rhs = -53242, |lhs - rhs| = 52950
A[ 5] = 687: lhs = 395, rhs = -53929, |lhs - rhs| = 54324
A[ 6] = 116: lhs = 511, rhs = -54045, |lhs - rhs| = 54556
A[ 7] = -257: lhs = 254, rhs = -53788, |lhs - rhs| = 54042
A[ 8] = 288: lhs = 542, rhs = -54076, |lhs - rhs| = 54618
A[ 9] = 592: lhs = 1134, rhs = -54668, |lhs - rhs| = 55802
A[ 10] = -385: lhs = 749, rhs = -54283, |lhs - rhs| = 55032
A[ 11] = -254: lhs = 495, rhs = -54029, |lhs - rhs| = 54524
A[ 12] = 816: lhs = 1311, rhs = -54845, |lhs - rhs| = 56156
A[ 13] = -946: lhs = 365, rhs = -53899, |lhs - rhs| = 54264
A[ 14] = -477: lhs = -112, rhs = -53422, |lhs - rhs| = 53310
A[ 15] = -61: lhs = -173, rhs = -53361, |lhs - rhs| = 53188
A[ 16] = 225: lhs = 52, rhs = -53586, |lhs - rhs| = 53638
A[ 17] = 174: lhs = 226, rhs = -53760, |lhs - rhs| = 53986
A[ 18] = -269: lhs = -43, rhs = -53491, |lhs - rhs| = 53448
A[ 19] = -408: lhs = -451, rhs = -53083, |lhs - rhs| = 52632 ** minimum so far
A[ 20] = 123: lhs = -328, rhs = -53206, |lhs - rhs| = 52878
A[ 21] = 124: lhs = -204, rhs = -53330, |lhs - rhs| = 53126
A[ 22] = -364: lhs = -568, rhs = -52966, |lhs - rhs| = 52398 ** minimum so far
A[ 23] = 41: lhs = -527, rhs = -53007, |lhs - rhs| = 52480
A[ 24] = -617: lhs = -1144, rhs = -52390, |lhs - rhs| = 51246 ** minimum so far
A[ 25] = 583: lhs = -561, rhs = -52973, |lhs - rhs| = 52412
A[ 26] = -860: lhs = -1421, rhs = -52113, |lhs - rhs| = 50692 ** minimum so far
A[ 27] = 39: lhs = -1382, rhs = -52152, |lhs - rhs| = 50770
A[ 28] = 465: lhs = -917, rhs = -52617, |lhs - rhs| = 51700
A[ 29] = -413: lhs = -1330, rhs = -52204, |lhs - rhs| = 50874
A[ 30] = -530: lhs = -1860, rhs = -51674, |lhs - rhs| = 49814 ** minimum so far
…
A[18048] = 381: lhs = -27278, rhs = -26256, |lhs - rhs| = 1022
A[18049] = 510: lhs = -26768, rhs = -26766, |lhs - rhs| = 2 ** minimum so far
A[18050] = -754: lhs = -27522, rhs = -26012, |lhs - rhs| = 1510
…
A[99990] = -196: lhs = -57461, rhs = 3927, |lhs - rhs| = 61388
A[99991] = 698: lhs = -56763, rhs = 3229, |lhs - rhs| = 59992
A[99992] = -141: lhs = -56904, rhs = 3370, |lhs - rhs| = 60274
A[99993] = 907: lhs = -55997, rhs = 2463, |lhs - rhs| = 58460
A[99994] = 158: lhs = -55839, rhs = 2305, |lhs - rhs| = 58144
A[99995] = 563: lhs = -55276, rhs = 1742, |lhs - rhs| = 57018
A[99996] = 851: lhs = -54425, rhs = 891, |lhs - rhs| = 55316
A[99997] = -12: lhs = -54437, rhs = 903, |lhs - rhs| = 55340
A[99998] = 703: lhs = -53734, rhs = 200, |lhs - rhs| = 53934
A[99999] = 200: lhs = -53534, rhs = 0, |lhs - rhs| = 53534
result: 2
I have a convenient random number generator program that can be told to generate N integers between -1000 and 1000 inclusive (and a whole lot more, but that's all that was necessary for this testing).