Given two arrays prices[], type[] and an integer S, the task is to check if two items can be selected from two different categories without exceeding the total price S. Each element in the type[] array denotes the category of the ith element and each element in the prices[] array denotes the price of the ith element.
Examples:
Input: S = 10, type[] = {0, 1, 1, 0}, prices[] = {3, 8, 6, 5}
Output: Yes
Explanation:
Elements prices[0] and prices[2] can be selected
Total prices = prices[0] + prices[2] = 3 + 6 = 9Input: S = 15, type[] = {0, 1, 1, 0}, prices[] = {5, 7, 6, 5}
Output: No
Explanation:
There is no possible solution such that total price is less than 15.
Approach: The idea is to iterate choose every possible pair using two nested loops. For each pair check that if their category is different and their total price is less than S, If yes then there is a way to pick two items otherwise there are no such pairs items.
Below is the implementation of the above approach:
C++14
// C++ implementation to check if// two items can be selected from// two different categories without// exceeding the total price#include <bits/stdc++.h>using namespace std;// Function to check if// two items can be selected from// two different categories without// exceeding the total pricestring check(int S, int prices[], int type[], int n){ // Loop to choose two different // pairs using two nested loops for (int j = 0; j < n; j++) { for (int k = j + 1; k < n; k++) { // Condition to check if the price // of these two elements is less than S if ((type[j] == 0 && type[k] == 1) || (type[j] == 1 && type[k] == 0)) { if (prices[j] + prices[k] <= S) { return "Yes"; } } } } return "No";}int main(){ int prices[] = { 3, 8, 6, 5 }; int type[] = { 0, 1, 1, 0 }; int S = 10; int n = 4; // Function Call cout << check(S, prices, type, n); return 0;} |
Java
// Java implementation to check if// two items can be selected from// two different categories without// exceeding the total priceimport java.util.*;class GFG{// Function to check if// two items can be selected from// two different categories without// exceeding the total pricestatic String check(int S, int prices[], int type[], int n){ // Loop to choose two different // pairs using two nested loops for (int j = 0; j < n; j++) { for (int k = j + 1; k < n; k++) { // Condition to check if the price // of these two elements is less than S if ((type[j] == 0 && type[k] == 1) || (type[j] == 1 && type[k] == 0)) { if (prices[j] + prices[k] <= S) { return "Yes"; } } } } return "No";}// Driver Codepublic static void main(String[] args){ int prices[] = { 3, 8, 6, 5 }; int type[] = { 0, 1, 1, 0 }; int S = 10; int n = 4; // Function Call System.out.print(check(S, prices, type, n));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to check if# two items can be selected from# two different categories without# exceeding the total price# Function to check if# two items can be selected from# two different categories without# exceeding the total pricedef check(S, prices, type1, n): # Loop to choose two different # pairs using two nested loops for j in range(0, n): for k in range(j + 1, n): # Condition to check if the price # of these two elements is less than S if ((type1[j] == 0 and type1[k] == 1) or (type1[j] == 1 and type1[k] == 0)): if (prices[j] + prices[k] <= S): return "Yes"; return "No";# Driver Codeprices = [ 3, 8, 6, 5 ];type1 = [ 0, 1, 1, 0 ];S = 10;n = 4;# Function Callprint(check(S, prices, type1, n));# This code is contributed by Code_Mech |
C#
// C# implementation to check if// two items can be selected from// two different categories without// exceeding the total priceusing System;class GFG{// Function to check if two items // can be selected from two // different categories without// exceeding the total pricestatic String check(int S, int []prices, int []type, int n){ // Loop to choose two different // pairs using two nested loops for(int j = 0; j < n; j++) { for(int k = j + 1; k < n; k++) { // Condition to check if the price // of these two elements is less than S if ((type[j] == 0 && type[k] == 1) || (type[j] == 1 && type[k] == 0)) { if (prices[j] + prices[k] <= S) { return "Yes"; } } } } return "No";}// Driver Codepublic static void Main(String[] args){ int []prices = { 3, 8, 6, 5 }; int []type = { 0, 1, 1, 0 }; int S = 10; int n = 4; // Function call Console.Write(check(S, prices, type, n));}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript implementation to check if// two items can be selected from// two different categories without// exceeding the total price// Function to check if two items // can be selected from two // different categories without// exceeding the total pricefunction check(S, prices, type, n){ // Loop to choose two different // pairs using two nested loops for(let j = 0; j < n; j++) { for(let k = j + 1; k < n; k++) { // Condition to check if the price // of these two elements is less than S if ((type[j] == 0 && type[k] == 1) || (type[j] == 1 && type[k] == 0)) { if (prices[j] + prices[k] <= S) { return "Yes"; } } } } return "No";}// Driver codelet prices = [ 3, 8, 6, 5 ];let type = [ 0, 1, 1, 0 ];let S = 10;let n = 4;// Function calldocument.write(check(S, prices, type, n));// This code is contributed by mukesh07</script> |
Output:
Yes
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
