Question

How would you find if numbers in an array element add up to a certain sum so for example if my array element consists of:

INPUT: 200, 10, 50, 20

and my output asks if these elements add to:

210? YES (200+10)

260? YES (200+10+50)

30? NO

What method would you suggest to look through the elements in an array (which im going to add through a text file) and determine if these sums exist in O(n^2)?

Answer 1

//File handling concept of C++ is used to look throug elements in an array inputted through file.

//run this on latest compiler since unordered_map is used
/*since for 30 it is showing No that means we are searching for subarray
beacuse if asked for subset the for 30 it should give Yes as result because 20 and 10 are there in array
*/

//Time complexity of this program=O(nlogn) which is better than O(n^2)


#include <fstream>
#include <iostream>
#include <sstream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
ifstream fin;
char filename[20];
//the file will have oly elements which are to be present in array
cout<<"Enter The File Name With Extension\n";
cin>>filename;
vector<int>vec;
fin.open(filename);

if (!fin)
{
cerr << "File not found." << endl;
return -1;
}
  
string line;
  
getline(fin, line);

istringstream iss(line);
int sum = 0, next = 0;
while (iss >> next)
vec.push_back(next);
fin.close();

cout<<"Enter required Sum :";
int k;
cin>>k;
int n=vec.size();
//If any subarray exists with sum=k then print Yes else No
unordered_map<int, int> prevSum;

int res = 0;

// Sum of elements so far.
int currsum = 0;

for (int i = 0; i < n; i++) {

// Add current element to sum so far.
currsum += vec[i];

// If currsum is equal to desired sum,
// then a new subarray is found. So
// increase count of subarrays.
if (currsum == sum)
res++;

// currsum exceeds given sum by currsum
// - sum. Find number of subarrays having
// this sum and exclude those subarrays
// from currsum by increasing count by
// same amount.
if (prevSum.find(currsum - sum) != prevSum.end())
res += (prevSum[currsum - sum]);

// Add currsum value to count of
// different values of sum.
prevSum[currsum]++;
}
if(res>0)
cout<<"YES\n";
   else
   cout<<"No\n";
return 0;

}