(Google Onsite) Array elements subtraction Game


  • 5
    D

    Imagine you have an array as [2, 7], subtract 2 from 7 and append result to the original array -> [2,7,5]

    [2, 7, 5] -> [2, 7, 5,3]
    [2,7,5,3] -> [2,7,5,3,1] or [2,7,5,3,4]

    [2,7,5,3,1] -〉[2,7,5,3,1, 6] or [2,7,5,3,1, 4]
    [2,7,5,3,1, 4] ->[2,7,5,3,1, 6, 4] or [2,7,5,3,1,4,6]

    [2,7,5,3,4] -〉 [2,7,5,3,4,1] -〉[2,7,5,3,4,1,6]

    Subtract between elements in the array until you cannot do so( no new element generated), The bold one are final results

    The question is to ask you output all the results in List<List<res>> format


  • 0
    A

    Could you please clarify? How does this transformation happen: [2, 7, 5] -> [2, 7, 5,3]

    Is 3 obtained by subtracting 2 from 5? So basically subtracting the first element from the last?
    If that is the case then I don't understand the next steps after that?


  • 0
    D

    @arxoclay u first subtract 2 from 7: 7-2=5 but 5 is already in [2,7,5], then do 5-2=3 and 3 is not in [2,7,5] so that you can append 3 to [2,7,5], then you have [2,7,5,3]


  • 0
    D

    @daniel.w.1 said in (Google Onsite) Array elements subtraction Game:

    @arxoclay u first subtract 2 from 7: 7-2=5 but 5 is already in [2,7,5], then do 5-2=3 and 3 is not in [2,7,5] so that you can append 3 to [2,7,5], then you have [2,7,5,3]

    and every single step you can only append 1 number to the back of array


  • 0

    @daniel.w.1 Could you explain more about?

    [2,7,5,3,1, 4] -> [2,7,5,3,1, 6, 4] or [2,7,5,3,1,4,6]

    It is clear that we get [2,7,5,3,1,4,6] from [2,7,5,3,1, 4] as we substract 1 from 7 and append 6 to the end of the list.

    But the more confusing part is how you get [2,7,5,3,1, 6, 4] from [2,7,5,3,1, 4] .

    Thank you very much for any explanation you provide.


  • 0
    D

    sorry, typo

    [2,7,5,3,1] -〉[2,7,5,3,1, 6] or [2,7,5,3,1, 4] we have two scenarios

    one scenario: [2,7,5,3,1, 6] ->[2,7,5,3,1, 6, 4]
    the other: [2,7,5,3,1, 4]->[2,7,5,3,1,4,6]


  • 0
    O
    void subtract(vector<int> curVec,unordered_set<int> curSet,unordered_set<int> add,vector<vector<int>>& res){
    	if(curVec.size()>1){
    		int last = curVec.back();
    		bool success = true;
    		for(int i=0;i<curVec.size()-1;i++){
    			int subEle = abs(last - curVec[i]);
    			if(curSet.find(subEle) == curSet.end() && add.find(subEle) == add.end())
    				add.insert(subEle);
    		}
    		if(add.size()==0)
    			res.push_back(curVec);
    		else{
    			unordered_set<int> tmp = add;
    			for(int ele:add){
    				curSet.insert(ele);
    				curVec.push_back(ele);
    				tmp.erase(ele);
    				subtract(curVec,curSet,tmp,res);
    				curSet.erase(ele);
    				curVec.pop_back();
    				tmp.insert(ele);
    			}
    		}
    	}
    }

  • 0
    A

    @daniel.w.1 How did you compute the following: [2,7,5,3] -> [2,7,5,3,1] or [2,7,5,3,4]

    Taking [2, 7, 5, 3] as an example, wouldn't the difference between the first and last element be 2-3 = -1. How did you obtain 1 and 4?


  • 0
    D

    @arxoclay cannot be negative number


  • 2

    Little follow-up: Instead of a list of all possible orders, just return a list of all reachable numbers. Can you do it in one line?


  • 0

    @daniel-w-1 is it specified that input array contains only 2 elements?


  • 0
    D

    @elmirap yes


  • 0
    X

    @OVSS I think the there is something wrong with the add. Here is my code below, I tested it works.

    void dfs(vector<vector<int> > & ans, vector<int> input, unordered_set<int> has) {
        if (input.size() == 0) return;
        unordered_set<int> added;
        int last = input.back();
        for(int i = 0; i < input.size() - 1; ++i ) {
            int diff = abs(last - input[i]);
            if(has.count(diff) == 0 && added.count(diff) == 0 && diff > 0) {
                added.insert(diff);
            }
        }
        if(added.size() == 0) ans.push_back(input);
        else {
            for(auto num : added) {
                has.insert(num);
                input.push_back(num);
                dfs(ans, input, has);
                input.pop_back();
                has.erase(num);
            }
        }
    }
    vector<vector<int> > solve(vector<int> input) {
        vector<vector<int> > ans;
        unordered_set<int> has(input.begin(), input.end());
        dfs(ans, input, has);
        return ans;
    }
    int main(int argc, const char * argv[]) {
        vector<int> input = {2,7};
        vector<vector<int> > ans = solve(input);
        for(auto v: ans) {
            for (auto e: v) cout<<e<<" ";
            cout<<endl;
        }
        return 0;
    }
    
    

  • 0

    @xinyao I also think there is a problem with add, I will the problem try later


  • 0
    O
    This post is deleted!

  • 1
    O
    void subtract(vector<int> curVec,unordered_set<int> curSet,unordered_set<int> add,vector<vector<int>>& res){
    	if(curVec.size()>1){
    		int last = curVec.back();
    		for(int i=0;i<curVec.size()-1;i++){
    			int subEle = abs(last - curVec[i]);
    			if(curSet.find(subEle) == curSet.end() && add.find(subEle) == add.end())
    				add.insert(subEle);
    		}
    		if(add.size()==0)
    			res.push_back(curVec);
    		else{
    			unordered_set<int> tmp = add;
    			for(int ele:add){
    				curSet.insert(ele);
    				curVec.push_back(ele);
    				tmp.erase(ele);
    				subtract(curVec,curSet,tmp,res);
    				curSet.erase(ele);
    				curVec.pop_back();
    				tmp.insert(ele);
    			}
    		}
    	}
    }
    
    vector<vector<int>> run(vector<int> test){
    	unordered_set<int> curSet;
    	unordered_set<int> add;
    	vector<vector<int>> res;
    	for(int ele:test)
    		curSet.insert(ele);
    	subtract(test,curSet,add,res);
    	return res;
    }
    
    int main(){
    	vector<int> test = {2,7};
    	vector<vector<int>> res = run(test);
    	for(auto i:res){
    		for(auto j:i)
    			cout<<j<<" ";
    		cout<<endl;
    	}
    	return 0;
    }

  • 1
    T

    @StefanPochmann , I'm not sure how to solve it in one line, My idea is to fine Greatest Common Divisor and fill from 1 * GCD , 2* GCD, 3 * GCD ...... Max(arr).

    coding with C#, not sure if it is correct.

           static List<int> cal(int[] arr) {
    
                Func<int, int, int> gcd = null;
    
                gcd = (a, b) => b == 0 ? a : gcd(b, a % b);
    
                int gcdNO = arr.Aggregate(gcd);
    
                return Enumerable.Range(1, arr.Max() / gcdNO).Select(x => x * gcdNO).ToList();
            }
    

    Thanks


  • 0

    @tangalai Yes, that's my way, too. For a one-liner, you might have to switch to another language :-P

    Here's Ruby:

    irb(main):005:0> def numbers(a) (0..a.max).step(a[0].gcd(a[1])).to_a[1..-1] end
    => :numbers
    
    irb(main):006:0> numbers([2, 7])
    => [1, 2, 3, 4, 5, 6, 7]
    
    irb(main):007:0> numbers([8, 2])
    => [2, 4, 6, 8]
    

  • 0
    T

    @StefanPochmann That is great follow up question, awesome.


  • 0
    S
    //just final result. comman devider
    public List<Integer> getFinalRst(int[] arr){
    	List<Integer> list = new LinkedList<>();
    	int min = Integer.MAX_VALUE;
    	int max = Integer.MIN_VALUE;
    	boolean gotMin = false;
    	
    	while(!gotMin){
    		for(int n:arr){
    			max = Math.max(max,n);
    			if(n%min!=0 && n%min<min){
    				 min = n%min;
    				 gotMin = true;
    			}
    		}	
    	}
    
    	for(int i=min;i<=max;i+=min)
    		list.add(i);
    
    	return list;
    }
    
    //all middle result . loops.
    public List<List<Integer>> getAllRst(int[] arr){
    	int l=0, r =1;
    	List<List<Integer>> lists = new LinkedList<>();
    	ArrayList<Integer> curList = new ArrayList<>();
    	HashSet<Integer> set = new HashSet<>();
    	for(int n:arr){
    		curList.add(n);
    		set.add(n);
    	}
    
    	while(r<curList.size()){
    		while(l<r){
    			int diff = Math.abs(curList.get(l) - curList.get(r));
    			while( l<r && (diff==0 || set.contains(diff)) ){
    				l++;
    				diff = Math.abs(curList.get(l) - curList.get(r));
    			}
    			if(l==r) continue;
    			curList.add(diff);
    			lists.add(curList);
    			curList = new ArrayList<>(curList);
    			set.add(diff);
    			l++;
    		}
    		r++;
    		l=0;
    	}
    
    	return lists;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.