# HackerRank Best spot problem solution

In this HackerRank Best spot problem solution In Chile, the land is partitioned into one large grid, where each element represents a land of size 1x1.

Shaka is a newcomer in Chile and is trying to start his own business. He is planning to build a store. He has his own ideas for the "perfect storm" which can be represented by a HxW grid. Element at position (i, j) represents the height of land at index (i, j) in the grid.

Shaka has purchased a land area that can be represented RxC grid (H <= R, W <= C). Shaka is interested in finding the best HxW sub-grid in the acquired land. In order to compare the possible sub-grids, Shaka will be using the sum of the squared difference between each cell of his "perfect storm" and it's the corresponding cell in the subgrid. Amongst all possible sub-grids, he will choose the one with the smallest sum.

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

static void bestSpot(int[][] land, int[][] store, int r, int c, int h, int w) {
long sumDiff = 0;
int m = r - h;
int n = c - w;
long minSum = Integer.MAX_VALUE;
int minCol = n;
int minRow = m;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
sumDiff = 0;

for (int k = 0; k < h; k++) {
for (int l = 0; l < w; l++) {
int z = land[i + k][j + l] - store[k][l];
sumDiff += z * z;
}
}

if (sumDiff == 0) {
minSum = sumDiff;
minRow = i;
minCol = j;
}
if (sumDiff < minSum) {
minSum = sumDiff;
minRow = i;
minCol = j;
} else if (sumDiff == minSum) {
if (minRow > i) {
minRow = i;
minCol = j;
} else if (minRow == i && minCol > j) {
minCol = j;
}
}
}
}

System.out.println(minSum);
System.out.println((minRow + 1) + " " + (minCol + 1));
}

public static void main(String[] args) throws IOException {

int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());

int[][] land = new int[r][c];

for (int i = 0; i < r; i++) {

for (int j = 0; j < c; j++) {
int item = Integer.parseInt(st.nextToken());
land[i][j] = item;
}
}

int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());

int[][] store = new int[h][w];

for (int iwItr = 0; iwItr < h; iwItr++) {

for (int j = 0; j < w; j++) {
int item = Integer.parseInt(st.nextToken());
store[iwItr][j] = item;
}
}

bestSpot(land, store, r, c, h, w);

br.close();
}
}```

## Problem solution in C++.

```#include <stdio.h>
#include <algorithm>
#include <stdio.h>
#include <ctime>
#include <math.h>
using namespace std;
#define N 510
#define M 1000000000
#define L 600100
int m[N][N], g[N][N], s[N][N];
int na, nb, a[L], b[L];
double PI=2*acos(0.0);
struct C
{
double r, i;
C(double r=0, double i=0): r(r), i(i) {}
};
inline C add(const C &a, const C &b) { return C(a.r+b.r, a.i+b.i); }
inline C sub(const C &a, const C &b) { return C(a.r-b.r, a.i-b.i); }
inline C mul(const C &a, const C &b) { return C(a.r*b.r-a.i*b.i, a.r*b.i+a.i*b.r); }
int z[L];
C v[L], u[L];
void fft(int n)
{
int i, j, k;
C t, a, b;
for(i=0; i<n; u[i]=v[z[i]], i++);
for(i=1; i<n; i*=2)
for(a=C(cos(PI/i), sin(PI/i)), j=0; j<n; j+=2*i)
for(b=C(1, 0), k=j; k<j+i; t=mul(u[k+i], b), u[k+i]=sub(u[k], t), u[k]=add(u[k], t), b=mul(b, a), k++);
}
long long fl(double x) { return x>0?x+0.5:x-0.5; }
void mul(int *a, int na, int *b, int nb, int *c, int &nc)
{
int i, j, n;
for(nc=na+nb-1, n=1; n<nc; n*=2);
for(z[0]=0, j=1; j<n; j*=2)
for(i=0; i<j; z[i]+=z[i], z[i+j]=z[i]+1, i++);
for(i=0; i<n; v[i]=C(a[i], b[i]), i++);
for(fft(n), u[n]=u[0], i=0; i<n; v[i]=mul(C((u[i].r+u[n-i].r)/2, (u[i].i-u[n-i].i)/2), C((u[i].i+u[n-i].i)/2, (u[n-i].r-u[i].r)/2)), i++);
for(fft(n), u[n]=u[0], i=0; i<n; c[i]=fl(u[n-i].r/n), i++);
}
int main()
{
int i, j, r, c, w, h, k, l, bi, bj;
scanf("%d%d", &h, &w);
for(na=h*w, i=0; i<h; i++)
for(j=0; j<w; scanf("%d", &m[i][j]), a[i*w+j]=m[i][j], j++);
scanf("%d%d", &r, &c);
for(i=0; i<r; i++)
for(j=0; j<c; scanf("%d", &g[i][j]), j++);
for(nb=0, i=r-1; i>=0; i--)
{
for(j=c-1; j>=0; b[nb++]=g[i][j], j--);
if(i>0)
for(j=0; j<w-c; b[nb++]=0, j++);
}
mul(a, na, b, nb, a, na);
for(i=0; i<h; i++)
for(j=0; j<w; s[i+1][j+1]=s[i][j+1]+s[i+1][j]-s[i][j]+m[i][j]*m[i][j], j++);
for(k=M, i=0; i+r<=h; i++)
for(j=0; j+c<=w; j++)
{
l=s[i+r][j+c]-s[i][j+c]-s[i+r][j]+s[i][j];
l-=2*a[(i+r-1)*w+j+c-1];
if(l<k) { bi=i; bj=j; k=l; }
}
for(i=0; i<r; i++)
for(j=0; j<c; k+=g[i][j]*g[i][j], j++);
printf("%d\n%d %d\n", k, bi+1, bj+1);
return 0;
}```

## Problem solution in C.

```#include <math.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double r;
double i;
} complex;
int mapidx(int i, int j, int C, int H);
void complexadd(complex *a, complex *b, complex *c);
void complexsub(complex *a, complex *b, complex *c);
void complexmul(complex *a, complex *b, complex *c);
void auxfft(complex *a, complex *omega, int N, int NN);
void fft(complex *a, complex *res, int N);
void ifft(complex *a, complex *res, int N);
void multiply(long long *a, long long *b, long long *res, int sizea, int sizeb);
int RC[500][500], HW[500][500];
long long dp[501][501];

int main() {
int R, C, H, W, i, j, idxi, idxj;
long long sum = 0, min = -1, *A, *B, *CC, t;
scanf("%d%d", &R, &C);
for (i = 0; i < R; i++)
for (j = 0; j < C; j++)
scanf("%d", &RC[i][j]);
scanf("%d%d", &H, &W);
for (i = 0; i < H; i++)
for (j = 0; j < W; j++) {
scanf("%d", &HW[i][j]);
sum += HW[i][j] * HW[i][j];
}
A = (long long *)malloc(R * C * sizeof(long long));
B = (long long *)malloc(H * C * sizeof(long long));
CC = (long long *)malloc((R * C + H * C - 1) * sizeof(long long));
for (i = 0; i <= R; i++)
dp[i][0] = 0;
for (i = 0; i <= C; i++)
dp[0][i] = 0;
for (i = 1; i <= R; i++)
for (j = 1; j <= C; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +
RC[i - 1][j - 1] * RC[i - 1][j - 1];
A[(i - 1) * C + j - 1] = RC[i - 1][j - 1];
}
for (i = 0; i < H; i++)
for (j = 0; j < C; j++)
B[i * C + j] = 0;
for (i = 0; i < H; i++)
for (j = 0; j < W; j++)
B[i * C + j] = HW[i][j];
for (i = 0; i < H * C / 2; i++) {
t = B[H * C - i - 1];
B[H * C - i - 1] = B[i];
B[i] = t;
}
multiply(A, B, CC, R * C, H * C);
for (i = 0; i <= R - H; i++)
for (j = 0; j <= C - W; j++) {
t = sum - 2 * CC[mapidx(i, j, C, H)] + dp[i + H][j + W] - dp[i + H][j] -
dp[i][j + W] + dp[i][j];
if (min == -1 || t < min) {
min = t;
idxi = i + 1;
idxj = j + 1;
}
}
printf("%lld\n", min);
printf("%d %d", idxi, idxj);
return 0;
}
int mapidx(int i, int j, int C, int H) { return i * C + j + H * C - 1; }
void complexadd(complex *a, complex *b, complex *c) {
c->r = a->r + b->r;
c->i = a->i + b->i;
return;
}
void complexsub(complex *a, complex *b, complex *c) {
c->r = a->r - b->r;
c->i = a->i - b->i;
return;
}
void complexmul(complex *a, complex *b, complex *c) {
c->r = a->r * b->r - a->i * b->i;
c->i = a->r * b->i + a->i * b->r;
return;
}
void auxfft(complex *a, complex *omega, int N, int NN) {
if (N == 1)
return;
int i, p;
complex *odd, *even;
odd = (complex *)malloc(N / 2 * sizeof(complex));
even = (complex *)malloc(N / 2 * sizeof(complex));
for (i = 0; i < N / 2; i++) {
even[i] = a[2 * i];
odd[i] = a[2 * i + 1];
}
auxfft(odd, omega, N / 2, NN);
auxfft(even, omega, N / 2, NN);
for (i = 0, p = NN / N; i < N / 2; i++) {
complex t;
complexmul(odd + i, omega + i * p, &t);
complexadd(even + i, &t, a + i);
complexsub(even + i, &t, a + i + N / 2);
}
free(odd);
free(even);
return;
}
void fft(complex *a, complex *res, int N) {
int i;
complex *omega = (complex *)malloc(N * sizeof(complex)), temp;
double angle = 8 * atan(1) / N;
for (i = 0; i < N; i++) {
omega[i].r = cos(i * angle);
omega[i].i = sin(i * angle);
res[i] = a[i];
}
auxfft(res, omega, N, N);
for (i = 1; i < N / 2; i++) {
temp = res[i];
res[i] = res[N - i];
res[N - i] = temp;
}
free(omega);
return;
}
void ifft(complex *a, complex *res, int N) {
int i;
complex *omega = (complex *)malloc(N * sizeof(complex));
double angle = 8 * atan(1) / N;
for (i = 0; i < N; i++) {
omega[i].r = cos(i * angle);
omega[i].i = sin(i * angle);
res[i] = a[i];
}
auxfft(res, omega, N, N);
for (i = 0; i < N; i++) {
res[i].r /= N;
res[i].i /= N;
}
free(omega);
return;
}
void multiply(long long *a, long long *b, long long *res, int sizea,
int sizeb) {
int n = 1, size = (sizea > sizeb) ? sizea : sizeb, i;
while (n <= 2 * size)
n <<= 1;
complex *A, *B, *AA, *BB;
A = (complex *)malloc(n * sizeof(complex));
B = (complex *)malloc(n * sizeof(complex));
AA = (complex *)malloc(n * sizeof(complex));
BB = (complex *)malloc(n * sizeof(complex));
for (i = 0; i < sizea; i++) {
A[i].r = a[i];
A[i].i = 0;
}
for (i = sizea; i < n; i++) {
A[i].r = 0;
A[i].i = 0;
}
for (i = 0; i < sizeb; i++) {
B[i].r = b[i];
B[i].i = 0;
}
for (i = sizeb; i < n; i++) {
B[i].r = 0;
B[i].i = 0;
}
fft(A, AA, n);
fft(B, BB, n);
for (i = 0; i < n; i++)
complexmul(AA + i, BB + i, A + i);
ifft(A, AA, n);
for (i = 0; i < sizea + sizeb - 1; i++)
res[i] = (long long)(AA[i].r + 0.5);
free(A);
free(B);
free(AA);
free(BB);
return;
}```