For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:
val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|
(Assume that the sum of zero elements equals zero.)
For a given array A, we are looking for such a sequence S that minimizes val(A,S).
Write a function:
int solution(int A[], int N);
that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.
For example, given array:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = -2your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..20,000];
- each element of array A is an integer within the range [−100..100].
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
for(int j=0;j<max+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
[7]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("sum=%d\n",sum);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("cnt[%d]=%d\n",i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-i]-1=%d\n",j,i,cnt[i]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,cnt[i]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::\n",j,i,cnt[i]);
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d\n",j,sval[i]);
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d sum=%d\n",j,sval[i]);
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d sum=%d\n",i,sval[i],ret,);
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
func.c: In function 'solution': func.c:42:86: error: expected ')' before ';' token printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)); ^ func.c:44:9: error: expected ';' before '}' token } ^
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
[7]
max=5 sum=10 cnt[1]=1 sval[0]=cnt[1]=1 sval[1]=sval[1-1]-1=0 cnt[2]=2 sval[0]=cnt[2]=2 sval[1]=cnt[2]=2 sval[2]=sval[2-2]-1=1 sval[3]=sval[3-2]-1=1 sval[4]=sval[4-2]-1=0 sval[5]=sval[5-2]-1=0 cnt[5]=1 sval[0]=cnt[5]=1 sval[1]=cnt[5]=1 sval[2]=cnt[5]=1 sval[3]=cnt[5]=1 sval[4]=cnt[5]=1 sval[5]=cnt[5]=1 sval[6]=sval[6-5]-1=0 sval[7]=sval[7-5]-1=0 sval[8]=sval[8-5]-1=0 sval[9]=sval[9-5]-1=0 sval[10]=sval[10-5]-1=0 sval[0]=1::ret=10 (sum-(2*0)=10 sval[1]=1::ret=10 (sum-(2*1)=8 sval[2]=1::ret=8 (sum-(2*2)=6 sval[3]=1::ret=6 (sum-(2*3)=4 sval[4]=1::ret=4 (sum-(2*4)=2 sval[5]=1::ret=2 (sum-(2*5)=0 sval[6]=0::ret=0 (sum-(2*6)=-2 sval[7]=0::ret=-2 (sum-(2*7)=-4 sval[8]=0::ret=-4 (sum-(2*8)=-6 sval[9]=0::ret=-6 (sum-(2*9)=-8 sval[10]=0::ret=-8 (sum-(2*10)=-10
function result: -7
max=7 sum=7 cnt[7]=1 sval[0]=cnt[7]=1 sval[7]=sval[7-7]-1=0 sval[0]=1::ret=7 (sum-(2*0)=7 sval[7]=0::ret=7 (sum-(2*7)=-7
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum/2+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum/2+1;i++){
if(sval[i]>=0){
printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
[7]
max=5 sum=10 cnt[1]=1 sval[0]=cnt[1]=1 sval[1]=sval[1-1]-1=0 cnt[2]=2 sval[0]=cnt[2]=2 sval[1]=cnt[2]=2 sval[2]=sval[2-2]-1=1 sval[3]=sval[3-2]-1=1 sval[4]=sval[4-2]-1=0 sval[5]=sval[5-2]-1=0 cnt[5]=1 sval[0]=cnt[5]=1 sval[1]=cnt[5]=1 sval[2]=cnt[5]=1 sval[3]=cnt[5]=1 sval[4]=cnt[5]=1 sval[5]=cnt[5]=1 sval[6]=sval[6-5]-1=0 sval[7]=sval[7-5]-1=0 sval[8]=sval[8-5]-1=0 sval[9]=sval[9-5]-1=0 sval[10]=sval[10-5]-1=0 sval[0]=1::ret=10 (sum-(2*0)=10 sval[1]=1::ret=10 (sum-(2*1)=8 sval[2]=1::ret=8 (sum-(2*2)=6 sval[3]=1::ret=6 (sum-(2*3)=4 sval[4]=1::ret=4 (sum-(2*4)=2 sval[5]=1::ret=2 (sum-(2*5)=0
function result: 7
max=7 sum=7 cnt[7]=1 sval[0]=cnt[7]=1 sval[7]=sval[7-7]-1=0 sval[0]=1::ret=7 (sum-(2*0)=7
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
//printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
//printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
//printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
//printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
//printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum/2+1;i++){
if(sval[i]>=0){
//printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
[7]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
//printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
//printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
//printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
//printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
//printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum/2+1;i++){
if(sval[i]>=0){
//printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
[7]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int max=0;
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
A[i]=val;
if(max<val)max=val;
sum+=val;
}
//printf("max=%d\n",max);
int *cnt=calloc(max+1,sizeof(int));
for(int i=0;i<N;i++){
cnt[A[i]]++;
}
//printf("sum=%d\n",sum);
int *sval=calloc(sum+1,sizeof(int));
for(int i=1;i<sum+1;i++){
sval[i]=-1;
}
for(int i=1;i<max+1;i++){
if(cnt[i]>0){
//printf("cnt[%d]=%d\n",i,cnt[i]);
for(int j=0;j<sum+1;j++){
if(sval[j]>=0){
sval[j]=cnt[i];
//printf("sval[%d]=cnt[%d]=%d\n",j,i,cnt[i]);
}
else if((j>=i)&&(sval[j-i]>0)){
sval[j]=sval[j-i]-1;
//printf("sval[%d]=sval[%d-%d]-1=%d\n",j,j,i,sval[j]);
}
}
}
}
int ret=sum;
for(int i=0;i<sum/2+1;i++){
if(sval[i]>=0){
//printf("sval[%d]=%d::ret=%d (sum-(2*%d)=%d\n",i,sval[i],ret,i,(sum-(2*i)));
ret=ret<(sum-(2*i))?ret:(sum-(2*i));
}
}
return ret;
}
The solution obtained perfect score.