In C code: All sorts of data can be thought of as points in high dimensional spa
ID: 673357 • Letter: I
Question
In C code:
All sorts of data can be thought of as points in high dimensional space. For example, a web page might be thought of as a point where each component is the number of words about a particular topic. For a bank, the components of the point might be related to your credit score and your debt to cash ratio, etc.
No matter what a point represents, it's important to be able to compute how similar two points are. For this assignment:
Create arrays for storing two points, both with 10 dimensions
Ask the user to input the components of the two points
print the distance between the two points
Distance is computed the same as it is for points in 2 or 3 d:
Your program should output should look something like this:
Explanation / Answer
Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[].
Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.
Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3 and 5 is 2.
Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Output: Minimum distance between 3 and 6 is 4.
Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Output: Minimum distance between 3 and 2 is 1.
Method 1 (Simple)
Use two loops: The outer loop picks all the elements of arr[] one by one. The inner loop picks all the elements after the element picked by outer loop. If the elements picked by outer and inner loops have same values as x or y then if needed update the minimum distance calculated so far.
#include <stdio.h>
#include <stdlib.h> // for abs()
#include <limits.h> // for INT_MAX
int minDist(int arr[], int n, int x, int y)
{
int i, j;
int min_dist = INT_MAX;
for (i = 0; i < n; i++)
{
for (j = i+1; j < n; j++)
{
if( (x == arr[i] && y == arr[j] ||
y == arr[i] && x == arr[j]) && min_dist > abs(i-j))
{
min_dist = abs(i-j);
}
}
}
return min_dist;
}
/* Driver program to test above fnction */
int main()
{
int arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
int y = 6;
printf("Minimum distance between %d and %d is %d ", x, y,
minDist(arr, n, x, y));
return 0;
}
Run on IDE
Output: Minimum distance between 3 and 6 is 4
Time Complexity: O(n^2)
Method 2 (Tricky)
1) Traverse array from left side and stop if either x or y is found. Store index of this first occurrence in a variable say prev
2) Now traverse arr[] after the index prev. If the element at current index i matches with either x or y then check if it is different from arr[prev]. If it is different then update the minimum distance if needed. If it is same then update prev i.e., make prev = i.
Thanks to wgpshashank for suggesting this approach.
#include <stdio.h>
#include <limits.h> // For INT_MAX
int minDist(int arr[], int n, int x, int y)
{
int i = 0;
int min_dist = INT_MAX;
int prev;
// Find the first occurence of any of the two numbers (x or y)
// and store the index of this occurence in prev
for (i = 0; i < n; i++)
{
if (arr[i] == x || arr[i] == y)
{
prev = i;
break;
}
}
// Traverse after the first occurence
for ( ; i < n; i++)
{
if (arr[i] == x || arr[i] == y)
{
// If the current element matches with any of the two then
// check if current element and prev element are different
// Also check if this value is smaller than minimm distance so far
if ( arr[prev] != arr[i] && (i - prev) < min_dist )
{
min_dist = i - prev;
prev = i;
}
else
prev = i;
}
}
return min_dist;
}
/* Driver program to test above fnction */
int main()
{
int arr[] ={3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
int y = 6;
printf("Minimum distance between %d and %d is %d ", x, y,
minDist(arr, n, x, y));
return 0;
}
Run on IDE
Output: Minimum distance between 3 and 6 is 1
Time Complexity: O(n)
Here in the above program i have taken the distance between 3 and 6 . you can specify your own input and select numbers where u want to find the distance
#include <stdio.h>
#include <stdlib.h> // for abs()
#include <limits.h> // for INT_MAX
int minDist(int arr[], int n, int x, int y)
{
int i, j;
int min_dist = INT_MAX;
for (i = 0; i < n; i++)
{
for (j = i+1; j < n; j++)
{
if( (x == arr[i] && y == arr[j] ||
y == arr[i] && x == arr[j]) && min_dist > abs(i-j))
{
min_dist = abs(i-j);
}
}
}
return min_dist;
}
/* Driver program to test above fnction */
int main()
{
int arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
int y = 6;
printf("Minimum distance between %d and %d is %d ", x, y,
minDist(arr, n, x, y));
return 0;
}