Shopping Options Amazon OA 2023 Solution

Contents

1 Shopping Options Amazon OA 2023 Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with Solution

Shopping Options Amazon OA 2023 Solution

Alternative Question: Find All Combination of Numbers Sum to Target

Given a positive integer, target, print all possible combinations of positive integers that sum up to the target number.

For example, if we are given input ‘5’, these are the possible sum combinations.

1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1

The output will be in the form a list of lists or an array of arrays. Each element in the list will be another list containing a possible sum combination.

Hint

Recursion
Two lists

SOLUTION

Program: Shopping Options Amazon OA Solution in C++

void print(vector<vector<int>> output){
  for(int i = 0; i < output.size(); i++){
    cout << "[ ";
    for(int j = 0; j < output[i].size(); j++){
      cout << output[i][j] << ", "; 
    }
    cout << "]" << endl;
  }
}
void print_all_sum_rec(
    int target,
    int current_sum,
    int start, vector<vector<int>>& output,
    vector<int>& result) {
  if (target == current_sum) {
    output.push_back(result);
  }
  for (int i = start; i < target; ++i) {
    int temp_sum = current_sum + i;
    if (temp_sum <= target) {
      result.push_back(i);
      print_all_sum_rec(target, temp_sum, i, output, result);
      result.pop_back();
    } else {
      return;
    }
  }
}
vector<vector<int>> print_all_sum(int target) {
  vector<vector<int>> output;
  vector<int> result;
  print_all_sum_rec(target, 0, 1, output, result);
  return output;
}
int main(int argc, const char* argv[]) {
  int n = 4;
  vector<vector<int>> result = print_all_sum(n);
  
  print (result);
}

Program: Shopping Options Amazon OA Solution in Java

class sumCombinations{
static void print(ArrayList<ArrayList<Integer>> arr) {
  for (int i = 0; i < arr.size(); i++) {
    System.out.print("[");
    for (int j = 0; j < arr.get(i).size(); j++) {
        System.out.print(arr.get(i).get(j) + ", ");
    }
    System.out.println("]");
}
}
static void print_all_sum_rec(
    int target,
    int current_sum,
    int start, ArrayList<ArrayList<Integer>> output,
    ArrayList<Integer> result) {
  if (target == current_sum) {
    output.add((ArrayList)result.clone());
  }
  for (int i = start; i < target; ++i) {
    int temp_sum = current_sum + i;
    if (temp_sum <= target) {
      result.add(i);
      print_all_sum_rec(target, temp_sum, i, output, result);
      result.remove(result.size() - 1);
    } else {
      return;
    }
  }
}
static ArrayList<ArrayList<Integer>> print_all_sum(int target) {
  ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
  ArrayList<Integer> result = new ArrayList<Integer>();
  print_all_sum_rec(target, 0, 1, output, result);
  return output;
}
public static void main(String[] args) {
  int n = 4;
  ArrayList<ArrayList<Integer>> result = print_all_sum(n);
  print (result);
}
}

Program: Shopping Options Amazon OA Solution in Python

import copy
def print_all_sum_rec(target, current_sum, start, output, result):
 if current_sum == target:
   output.append(copy.copy(result))
 for i in range(start, target):
   temp_sum = current_sum + i
   if temp_sum <= target:
     result.append(i)
     print_all_sum_rec(target, temp_sum, i, output, result)
     result.pop()
   else:
     return
def print_all_sum(target):
 output = []
 result = []
 print_all_sum_rec(target, 0, 1, output, result)
 return output
n = 4
res = print_all_sum(n)
print(res)

Shopping Options Amazon OA 2023 Solution

SOLUTION

Amazon OA 2023 Questions with Solution