Demo entry 3548629

yuhao

   

Submitted by anonymous on Jan 13, 2016 at 22:55
Language: C++. Code size: 3.6 kB.

//
//  KCGQ4.cpp
//
//  Created by Yuhao on 1/10/16.
//  Copyright © 2016 Yuhao. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    
    //define variables for use
    int N(0),i(0),j(0),leftPointer(0),rightPointer(0),sumThree(0),tempInput(0);
    
    //reads a sequence of numbers from standard input
    //example input: "-1 -1 0 2 -2 -3 5;"
    //notice that the sequence should end with a ";"
    vector<int> seq;
    cout<<"Please enter the sequence with integers separated by space and ended with ';'"<<endl;
    while(cin>>tempInput){
        seq.push_back(tempInput);
    }
    
    //sort the sequence into ascending order
    sort(seq.begin(),seq.end());
    N=(int)seq.size();
    
    //initialize vector for storing solutions
    vector<vector<int>> solution;
    vector<int> tempVector(3);
    
    //search for triples
    for (i=0;i<N;i++){
        //check whether the current first element is the same as the previous one
        //avoiding duplicate answers.
        if((i==0) || (i>0 && seq[i] != seq[i-1])){
            //initialize two pointers for rest two elements
            leftPointer=i+1;
            rightPointer=N-1;
            
            //search for rest two elements in triple, only need O(N) time as the sequence is sorted
            while (leftPointer<rightPointer){
                sumThree=seq[i]+seq[leftPointer]+seq[rightPointer];
                
                if (sumThree>0){
                    //sum exceeds zero, need smaller element
                    rightPointer=rightPointer-1;
                }
                else if(sumThree<0){
                    //sum less than zero, need larger element
                    leftPointer=leftPointer+1;
                }
                else{
                    //solution found, save solution
                    tempVector[0]=seq[i];
                    tempVector[1]=seq[leftPointer];
                    tempVector[2]=seq[rightPointer];
                    solution.push_back(tempVector);
                    
                    //jump to the next different element for second element
                    //avoiding duplicate answers
                    while((leftPointer+1)<rightPointer && seq[leftPointer]==seq[leftPointer+1]){
                        leftPointer=leftPointer+1;
                    }
                    leftPointer++;
                    
                    //jump to the next different element for third element
                    //avoiding duplicate answers
                    while((rightPointer-1)>leftPointer && seq[rightPointer]==seq[rightPointer-1]){
                        rightPointer=rightPointer-1;
                    }
                    rightPointer--;
                }
            }
        }
    }
    
    //Print out solutions found
    if (solution.size()==0){
        cout<<"No solution found!"<<endl;
    }
    else{
        for (i=0;i<solution.size();i++){
            cout<<"No."<<(i+1)<<" triple: ";
            for (j=0;j<3;j++){
                cout<<solution[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    //sample outputs:
    //
    //Please enter the sequence with integers separated by space and ended with ';'
    //1 -1 0 2 -2 -3 5;
    //No.1 triple: -3 -2 5
    //No.2 triple: -3 1 2
    //No.3 triple: -2 0 2
    //No.4 triple: -1 0 1
    
    
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).