Interview Question
Web DevelopersCountry: United States
Interview Type: Phone Interview
@ChrisK I thought about that but I got stuck, I can see a linear algorithm using two counters if you have a number to guide the search. I mean given the next array
[10, 20, 35, 40, 75, 90, 180]
If you have two counters one for the lower element and one for the higher element how you do modify them? Potentially any number except the two first ones and the last one can be used to generate a solution.
I have been thinking about some other approaches but none worked.
@ChrisK that is the problem I was encountering if you have the desired sum you can guide the search using two counters but on the given problem you have length of the array - 2 possible desired sums (the two first elements of the array can't be the desired sum for obvious reasons) so you can't use the algorithm as is to solve the problem.
public class ArraySum {
public static void main(String[] args) {
checksuma ch = new checksuma();
int as[] = { 20, 40 ,20};
System.out.println(ch.methsummc(as));
;
}
}
class checksuma {
boolean b = false;
public boolean methsummc(int ex[]) {
for (int i = 0; i < ex.length; i++) {
for (int j = 0; j < ex.length; j++) {
for (int k = j + 1; k < ex.length; k++) {
if (ex[i] == ex[j] + ex[k]) {
b = true;
}
}
}
}
return b;
}
}
bool is_sum_of_two_elem_present(vector<int>&& arr) {
sort(arr.begin(), arr.end());
for (auto target = arr.rbegin(); target != next(arr.rend(), -2); ++target) {
auto to_find = *target - *next(target);
if (binary_search(next(target,2), arr.rend(), to_find, std::greater<int>())) return true;
}
return false;
function check(arr){
var a = arr.sort()
console.log(a)
for(var i = 0; i < a.length -2; i++){
var t = ( Math.abs(a[i+2]) == Math.abs(a[i]) + Math.abs(a[i+1]) )
if(t){
return true
}
}
return false;
}
console.log(check([1,2,3])) // true
console.log(check([1,7,6])) // true
console.log(check([-1,9,8])) // true
console.log(check([-1,4,8])) // false
console.log(check([-3,-5,-8])) // true
x = [10,20,30];
for(var i= 0; i < x.length; i++)
{
a =0;
b=0;
c= 0;
if(i < x.length){
a=i;
}
else{
a=0;
}
if(a < x.length-1){
b=a+1;
}
else{
b=0;
}
if(b < x.length-1){
c=b+1;
}
else{
c=0;
}
if(x[a] == x[b] + x[c]) {
console.log("true" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
else{
console.log("false" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
}
Try copy pasting in console and this will work fine for array of three numbers.
try copy pasting in console and this snippet will work for array of three int.
for(var i= 0; i < x.length; i++)
{
a =0;
b=0;
c= 0;
if(i < x.length){
a=i;
}
else{
a=0;
}
if(a < x.length-1){
b=a+1;
}
else{
b=0;
}
if(b < x.length-1){
c=b+1;
}
else{
c=0;
}
if(x[a] == x[b] + x[c]) {
console.log("true" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
else{
console.log("false" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
}
I have been trying to find a solution to improve the cost but I haven't been able to. Solution with O(n^2) time and O(n) memory
- Fernando August 01, 2017