Sid is a superior salesperson. So he gets a task from his boss. The task is that he will be given some number of products say k (All the products are same) and he has to travel N cities [1...N] to sell them. The main objective of the task is that he has to try to sell the product at higher price than previous city. For example if he sells a product at 100 Rs in one city then he has to try to sell the next product greater than 100 Rs in the next city and so on.
He travels all the cities and write down all the selling amounts. Now He wants to calculate maximum number of cities in which he could follow this increasing trend. And the maximum total prime money he could make in those cities. Help him in  finding this.
Note : Number of products will always be equal to number of cities. 
 
Example 1:
Input:
N = 9
A[] = {4, 2, 3, 5, 1, 6, 7, 8, 9}
Output:
5 7
Explanation:
5 cities are maximum number of 
cities in which the trend 
followed, And  amount in those 
cities were 1, 6, 7, 8, 9. 
Out of  these  amounts only 
7 is prime money.
 
Example 2:
Input:
N = 10
A[] = {2, 3, 5, 7, 4, 1, 6, 5, 4, 8}
Output:
4 17
Explanation:
4 cities are maximum number of 
cities in which the trend 
followed, And  amount in those 
cities were 2, 3, 5, 7. 
Out of  these amounts, maximum
total prime money is 2+3+5+7=17.
 
Example 3:
Input:
N = 5
A[] = {2, 2, 2, 2, 2}
Output:
1 2
Explanation:
He was successful in one city 
only, And maximum total prime 
money is 2.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function primeMoney() which takes the array A[] and its size N as inputs and returns the maximum number of cities and maximum total prime money as a pair. 
Expected Time Complexity: O(N. sqrt(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5 }

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def primeMoney(self, arr, n):
        # return (0,0)


Solutions:
primes = [2, 3]

class Solution:

	def primeMoney(self, arr, n):
		maxi = max(arr)
		i = primes[-1] + 2
		while maxi >= i:
			flag = True
			for item in primes:
				if i % item == 0:
					flag = False
					break
			if flag:
				primes.append(i)
			i += 2
		setti = set(primes)
		count = 0
		summa = 0
		last = 0
		temp_count = 0
		temp_summa = 0
		for item in arr:
			if item > last:
				temp_count += 1
				if item in setti:
					temp_summa += item
			else:
				if temp_count > count:
					count = temp_count
					summa = temp_summa
				elif temp_count == count:
					summa = max(summa, temp_summa)
				temp_count = 1
				if item in setti:
					temp_summa = item
				else:
					temp_summa = 0
			last = item
		if temp_count > count:
			count = temp_count
			summa = temp_summa
		elif temp_count == count:
			summa = max(summa, temp_summa)
		return (summa, count)


class Solution:

	def primeMoney(self, arr, n):
		cities_count = 0
		prime_sum = 0
		prev_price = 0
		temp_cities_count = 0
		temp_prime_sum = 0
		for i in range(n):
			price = arr[i]
			if price > prev_price:
				temp_cities_count += 1
				temp_prime_sum += self.is_prime_number(price)
				if i == n - 1:
					(cities_count, prime_sum) = self.check_answer_condition(temp_cities_count, temp_prime_sum, cities_count, prime_sum)
			else:
				(cities_count, prime_sum) = self.check_answer_condition(temp_cities_count, temp_prime_sum, cities_count, prime_sum)
				temp_cities_count = 1
				temp_prime_sum = self.is_prime_number(price)
			prev_price = price
		return (prime_sum, cities_count)

	def check_answer_condition(self, temp_cities_count, temp_prime_sum, cities_count, prime_sum):
		if temp_cities_count > cities_count:
			cities_count = temp_cities_count
			prime_sum = temp_prime_sum
		elif temp_cities_count == cities_count and temp_prime_sum > prime_sum:
			cities_count = temp_cities_count
			prime_sum = temp_prime_sum
		return (cities_count, prime_sum)

	def is_prime_number(self, number):
		if number == 1:
			return False
		if number == 2 or number == 3:
			return number
		from math import sqrt
		for i in range(2, int(sqrt(number)) + 1):
			if number % i == 0:
				return False
		return number


class Solution:

	def prime(self, n):
		if n == 1:
			return 0
		for i in range(2, int(n ** (1 / 2)) + 1):
			if n % i == 0:
				return 0
		return 1

	def primeMoney(self, arr, n):
		maxi = -1
		last_value = -1
		l = -1
		r = -1
		count = 0
		total_prime = 0
		for i in range(0, n):
			if arr[i] > last_value:
				last_value = arr[i]
				count += 1
			else:
				if count > maxi:
					maxi = count
					r = i - 1
					l = i - count
					total_prime = 0
					for k in range(l, r + 1):
						total_prime += self.prime(arr[k]) * arr[k]
				elif count == maxi:
					t_l = i - count
					t_r = i - 1
					t_total_prime = 0
					for k in range(t_l, t_r + 1):
						t_total_prime += self.prime(arr[k]) * arr[k]
					if t_total_prime > total_prime:
						total_prime = t_total_prime
						r = i - 1
						l = i - count
				count = 1
				last_value = arr[i]
		if count > maxi:
			maxi = count
			r = n - 1
			l = n - count
			total_prime = 0
			for i in range(l, r + 1):
				total_prime += self.prime(arr[i]) * arr[i]
		elif count == maxi:
			t_l = n - count
			t_r = n - 1
			t_total_prime = 0
			for k in range(t_l, t_r + 1):
				t_total_prime += self.prime(arr[k]) * arr[k]
			if t_total_prime > total_prime:
				total_prime = t_total_prime
		return (total_prime, maxi)