zarrym911's blog

By zarrym911, history, 4 years ago, In English

An airline company wishes to establish a flight service in a new country. The company wants to provide flight service in such a way that will cover all the cities in the country with a minimum number of flights. Given the coordinates of all the cities in the country, the company has to determine the minimum number of straight routes necessary to cover all the cities. Write an algorithm to help the company find the minimum number of straight routes necessary to cover all the cities.

Input

The first line of the input consists of: two space-separated integers: numCities, representing the number of cities in the country(N). The next N lines consist of two space-separated integers: coordX and coordY representing the X and Y coordinates of the cities, respectively.

Output

Print an integer representing the minimum number of straight routes necessary to cover all the cities.

Constraints

0 <= numCitiess <= 10^4

-10^3 < coordX, coordy < 10^3

Example

INPUT:

8

1 4

2 3

2 1

3 2

4 1

5 0

4 3

5 4

OUTPUT:

2

Explanation:

The points (2,1)(3,2)((4,3)(5,4) fall on a straight line and the points (1,4)(2,3)(3,2)(4,1)(5,0) fall on another straight line.

Full text and comments »

  • Vote: I like it
  • -22
  • Vote: I do not like it

By zarrym911, history, 4 years ago, In English

Walmart came in our college for hiring and there was only one coding problem in the first round which took place on Hackerearth. I wasn't able to sove the question, but I am really curious about how to solve this question. So, here goes the question:

TIME LIMIT PER TEXT CASE: 1 sec. You are given a 1-indexed array A with N integers. Find the index i such that 1 < i < N and difference between the number of integers greater than A[i] in the range 1 to i-1 and the number of integers lesser than A[i] in the range i+1 to N is maximum.

INPUT: First line contains a number N as input. Next line contains N space seperated integers.

OUTPUT: In the output you need to print the maximum absolute difference that is obtained.

CONSTRAINT: 3 <= N <= 10^5; 1 <= A[i] <= 10^9

SAMPLE INPUT 1: 4 1 4 2 7

SAMPLE OUTPUT 1: 1

EXPLANATION: If we choose value 2 i.e. the index 3 then total elements greater than 2 to its left side is 1 and total elements lesser than 2 to es nget e 0 so the difference is 1 which is the maximum in the array.

NOTE: I have written the exact question which was provided to us.

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it