Maximize the profit after selling the tickets | Set 2 (For elements in range [1, 10^6])
Given an array, arr[] of size N where arr[i] represents the number of tickets, the ith seller has and a positive integer K. The price of a ticket is the number of tickets remaining with the ticket seller. They can sell a total of K tickets. Find the maximum amount they can earn by selling K tickets. Give the answer modulo 109 + 7.
Examples:
Input: seats[] = {2, 1, 1}, K= 3
Output: 4
Explanation: Consider 0 based indexing. For first two turns the 2nd seller sells. For the third turn either 0th or 2nd seller can sell. So the total becomes 6 + 5 + 4 = 15.Input: seats[] = {2, 3, 4, 5, 1}, K = 6
Output: 22
Approach : The naive approach and efficient approach is discussed in this article.
The approaches mentioned in the article can be optimized further by observing that since all the elements are less than or equal to 10^6, therefore, we can store the frequency of all the elements in an array A[]. Follow the steps below to solve the problem:
- Create an array A[] that stores the frequency of each element of the array arr[].
- Iterate in the range [0, N-1] using the variable i and increment the value of A[arr[i]] by 1.
- Initialize a variable, say j that keeps the track of the position of the array elements.
- Iterate in the range [0, 1000000] using the variable i and perform the following steps:
- While A[i] != 0, modify the value of arr[j] as i and decrement the value of A[i] by 1.
- Initialize two variable, say i as N-1 and j as N-2.
- Initialize a variable, say ans as 0.
- Iterate while k>0 and j>=0 and perform the following steps:
- If arr[i] > arr[j],
- Then add min(K, i-j)*arr[i] to the answer.
- Decrement the value of K by i-j and decrement the value of arr[i] by 1.
- Otherwise,
- Decrement the value of j while arr[j] = arr[i].
- Then add min(K, i-j)*arr[i] to the answer ans.
- Decrement the value of K by i-j and decrement the value of arr[i] by 1.
- If arr[i] > arr[j],
- Iterate while K>0 and arr[i]>0 and perform the following steps:
- Then add min(K, N)*arr[i] to the answer ans.
- Decrement the value of K by N and decrease the value of arr[i] by 1.
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find maximum profit // after selling K tickets int maxAmount( int n, int k, int arr[]) { // Frequency array to store freq // of every element of the array int A[1000001] = { 0 }; for ( int i = 0; i < n; i++) { A[arr[i]]++; } int j = 0; // Modify the arr[] so that the // array is sorted in O(N) for ( int i = 0; i < 1000001; i++) { while (A[i] != 0) { arr[j++] = i; A[i]--; } } // Variable to store answer long long int ans = 0; int mod = 1e9 + 7; int i = n - 1; j = n - 2; // Traverse the array while K>0 // and j>=0 while (k > 0 && j >= 0) { // If arr[i] > arr[j] then // ticket can be brought from // counter [j+1, N] if (arr[i] > arr[j]) { ans = ans + min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } else { // If arr[j] == arr[i] decrement j until // arr[j] != arr[i] while (j >= 0 && arr[j] == arr[i]) j--; if (j < 0) break ; // Sell tickets from counter [j+1, N] ans = ans + min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } } // All elements of array are equal // Send tickets from each counter 1 // time until K > 0. while (k > 0 && arr[i] != 0) { ans = ans + min(n, k) * arr[i]; k -= n; arr[i]--; } ans = ans % mod; // Converting answer from long long // to int int x = ans; return x; } // Driver Code int main() { // Given Input int n = 5; int k = 3; int arr[n] = { 4, 3, 6, 2, 4 }; // Function Call int ans = maxAmount(n, k, arr); cout << ans; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find maximum profit // after selling K tickets static int maxAmount( int n, int k, int arr[]) { // Frequency array to store freq // of every element of the array int A[] = new int [ 1000001 ]; for ( int i = 0 ; i < n; i++) { A[arr[i]]++; } int j = 0 ; // Modify the arr[] so that the // array is sorted in O(N) for ( int i = 0 ; i < 1000001 ; i++) { while (A[i] != 0 ) { arr[j++] = i; A[i]--; } } // Variable to store answer int ans = 0 ; int mod = ( int ) (1e9 + 7 ); int i = n - 1 ; j = n - 2 ; // Traverse the array while K>0 // and j>=0 while (k > 0 && j >= 0 ) { // If arr[i] > arr[j] then // ticket can be brought from // counter [j+1, N] if (arr[i] > arr[j]) { ans = ans + Math.min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } else { // If arr[j] == arr[i] decrement j until // arr[j] != arr[i] while (j >= 0 && arr[j] == arr[i]) j--; if (j < 0 ) break ; // Sell tickets from counter [j+1, N] ans = ans + Math.min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } } // All elements of array are equal // Send tickets from each counter 1 // time until K > 0. while (k > 0 && arr[i] != 0 ) { ans = ans + Math.min(n, k) * arr[i]; k -= n; arr[i]--; } ans = ans % mod; // Converting answer from long long // to int int x = ans; return x; } // Driver Code public static void main(String[] args) { // Given Input int n = 5 ; int k = 3 ; int arr[] = { 4 , 3 , 6 , 2 , 4 }; // Function Call int ans = maxAmount(n, k, arr); System.out.print(ans); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to find maximum profit # after selling K tickets def maxAmount(n, k, arr): # Frequency array to store freq # of every element of the array A = [ 0 for i in range ( 1000001 )] for i in range (n): A[arr[i]] + = 1 j = 0 # Modify the arr[] so that the # array is sorted in O(N) for j in range ( 1000001 ): while (A[i] ! = 0 ): arr[j] = i; j + = 1 A[i] - = 1 # Variable to store answer ans = 6 mod = 1000000007 i = n - 1 j = n - 2 # Traverse the array while K>0 # and j>=0 while (k > 0 and j > = 0 ): # If arr[i] > arr[j] then # ticket can be brought from # counter [j+1, N] if (arr[i] > arr[j]): ans = ans + min (k, (i - j)) * arr[i] k = k - (i - j) arr[i] - = 1 else : # If arr[j] == arr[i] decrement j until # arr[j] != arr[i] while (j > = 0 and arr[j] = = arr[i]): j - = 1 if (j < 0 ): break # Sell tickets from counter [j+1, N] ans = ans + min (k, (i - j)) * arr[i] k = k - (i - j) arr[i] - = 1 # All elements of array are equal # Send tickets from each counter 1 # time until K > 0. while (k > 0 and arr[i] ! = 0 ): ans = ans + min (n, k) * arr[i] k - = n arr[i] - = 1 ans = ans % mod # Converting answer from long long # to int x = ans return x # Driver Code if __name__ = = '__main__' : # Given Input n = 5 k = 3 arr = [ 4 , 3 , 6 , 2 , 4 ] # Function Call ans = maxAmount(n, k, arr) print (ans) # This code is contributed by avijitmondal1998 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find maximum profit // after selling K tickets static int maxAmount( int n, int k, int []arr) { // Frequency array to store freq // of every element of the array int i; int []A = new int [1000001]; Array.Clear(A,0,1000001); for (i = 0; i < n; i++) { A[arr[i]]++; } int j = 0; // Modify the arr[] so that the // array is sorted in O(N) for (i = 0; i < 1000001; i++) { while (A[i] != 0) { arr[j++] = i; A[i]--; } } // Variable to store answer int ans = 0; int mod = 1000000007; i = n - 1; j = n - 2; // Traverse the array while K>0 // and j>=0 while (k > 0 && j >= 0) { // If arr[i] > arr[j] then // ticket can be brought from // counter [j+1, N] if (arr[i] > arr[j]) { ans = ans + Math.Min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } else { // If arr[j] == arr[i] decrement j until // arr[j] != arr[i] while (j >= 0 && arr[j] == arr[i]) j--; if (j < 0) break ; // Sell tickets from counter [j+1, N] ans = ans + Math.Min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } } // All elements of array are equal // Send tickets from each counter 1 // time until K > 0. while (k > 0 && arr[i] != 0) { ans = ans + Math.Min(n, k) * arr[i]; k -= n; arr[i]--; } ans = ans % mod; // Converting answer from long long // to int int x = ans; return x; } // Driver Code public static void Main() { // Given Input int n = 5; int k = 3; int []arr = { 4, 3, 6, 2, 4 }; // Function Call int ans = maxAmount(n, k, arr); Console.Write(ans); } } // This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript program for the above approach; // Function to find maximum profit // after selling K tickets function maxAmount(n, k, arr) { // Frequency array to store freq // of every element of the array let A = new Array(1000001).fill(0); for (let i = 0; i < n; i++) { A[arr[i]]++; } let j = 0; // Modify the arr[] so that the // array is sorted in O(N) for (let i = 0; i < 1000001; i++) { while (A[i] != 0) { arr[j++] = i; A[i]--; } } // Variable to store answer let ans = 0; let mod = 1e9 + 7; let i = n - 1; j = n - 2; // Traverse the array while K>0 // and j>=0 while (k > 0 && j >= 0) { // If arr[i] > arr[j] then // ticket can be brought from // counter [j+1, N] if (arr[i] > arr[j]) { ans = ans + Math.min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } else { // If arr[j] == arr[i] decrement j until // arr[j] != arr[i] while (j >= 0 && arr[j] == arr[i]) j--; if (j < 0) break ; // Sell tickets from counter [j+1, N] ans = ans + Math.min(k, (i - j)) * arr[i]; k = k - (i - j); arr[i]--; } } // All elements of array are equal // Send tickets from each counter 1 // time until K > 0. while (k > 0 && arr[i] != 0) { ans = ans + Math.min(n, k) * arr[i]; k -= n; arr[i]--; } ans = ans % mod; // Converting answer from long long // to let let x = ans; return x; } // Driver Code // Given Input let n = 5; let k = 3; let arr = [4, 3, 6, 2, 4]; // Function Call let ans = maxAmount(n, k, arr); document.write(ans); // This code is contributed by Potta Lokesh </script> |
15
Time Complexity:O(N)
Auxiliary Space: O(N)