Missing Numbers Codechef Solution

Missing Numbers Codechef Solution

Alice (uniformly and independently) randomly picks two integers a,b from the range [1,104], and writes down the values of a+b, a−b, a⋅b and ⌊ab⌋ (integer division) in some random order. Unfortunately, she forgot the values of a and b. You need to help her to find out if there exists two integers a,b such that 1≤a,b≤104 and a+b, a−b, a⋅b, ⌊ab⌋ are the numbers she has written down.

If a solution exists, it is guaranteed to be unique.

Input Format

  • The first line of input contains a single integer T, denoting the number of testcases. The description of T testcases follows.
  • Each testcase consists of a single line of input, containing four space-separated integers A,B,C,D — the values written down by Alice. It is guaranteed that at most one of the four numbers A,B,C,D will be negative.

Output Format
For each testcase, output in a single line, separated by a space, the two numbers Alice has chosen in order (i.e, if the solution is a=1 and b=2, print 1 2 and not 2 1). If there does not exist any such choice of integers, print −1 twice, separated by a space, instead.

Constraints

  • 1≤T≤105
  • −109≤A,B,C,D≤109
  • At most one of A,B,C,D is negative.


Subtasks
Subtask #1 (100 points):
Original constraints

Sample Input 1
2
-1 72 0 17
1 4 5 6

Sample Output 1
8 9
-1 -1

Explanation

  • Test case 1: With a=8,b=9 we obtain 8+9=17,8−9=−1,8⋅9=72,⌊89⌋=0 which are exactly the 4 numbers written down by Alice.
  • Test case 2: It can be shown that no choice of integers a,b can produce the given 4 numbers.

SOLUTION

Program: Missing Numbers Codechef Solution in Python

for _ in range(int(input())):
    s1, s2, l1, l2 = sorted(list(map(int, input().split())))
    pos_comb, l, found = set(), [s1, s2, l1, l2], False
    
    for num1 in [l1, l2]:
        for num2 in [s1, s2]:
            if (num1+num2)%2==0:
                a = (num1+num2)//2
                b = (num1-num2)//2
                if 0 < a <= 10000 and 0 < b <= 10000 and l == sorted([a+b, a-b, a*b, a//b]):
                    print(a, b)
                    found = True
                    break
        if found:
            break
            
    if not found:
        print(-1, -1)

Program: Missing Numbers Codechef Solution in C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long int arr[4];
        for(int i=0; i<4; i++)
        {
            cin>>arr[i];
        }
        sort(arr, arr+4);
        long long int add, sub, mul, dvi;
        if(arr[0]<0){
            sub = arr[0];
            dvi = arr[1];
            if(arr[3]-arr[2]==1){
                if(arr[2]==5 && arr[3]==6 && arr[0]==-1 && arr[1]==0)
                {
                    mul = arr[3];
                    add = arr[2];
                }
                else
                {
                    mul = arr[2];
                    add = arr[3];
                }
            }
            else
            {
                mul = arr[3];
                add = arr[2];
            }
        }
        else if(arr[0]>0)
        {
                
            if(arr[3]-arr[2]==1)
            {
                if(arr[2]==5 && arr[3]==6 && arr[1]==1 && arr[0]==1)
                {
                    mul = arr[3];
                    add = arr[2];
                }
                else
                {
                    mul = arr[2];
                    add = arr[3];
                }
                sub = arr[0];
                dvi = arr[1];
            }
            else
            {
                dvi = arr[0];
                sub = arr[1];
                add = arr[2];
                mul = arr[3];
            }
            
        }
        else if(arr[0]==0)
        {
            if(arr[3]-arr[2]==1 && arr[1]==1 && arr[2]==1)
            {
                add = arr[3];
                mul = arr[2];
            }
            else 
            {
                add = arr[2];
                mul = arr[3];
            }
            sub = arr[0];
            dvi = arr[1];
        }
        long long int n1, n2;
        n1 = (add + sub)/2;
        n2 = (add - sub)/2;
        if(n1<=10000 && n2<=10000 && n1>0 && n2>0 && ((n1*n2) == mul) && ((n1/n2) == dvi))
        {
            cout<<n1<<" "<<n2<<endl;
        }
        else
        {
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}

Program: Missing Numbers Codechef Solution in Java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		InputReader in = new InputReader(inputStream);
		int T = in.nextInt();
		while (T-- > 0) {
			int[] arr = new int[4];
			for(int i=0;i<4;i++) {
			    arr[i] = in.nextInt();
			}
			Arrays.sort(arr);
			boolean found = false;
			for(int b=0;b<3;b++) {
			    if(found)
			        break;
			    for(int a=b+1;a<4;a++) {
			        if(found)
			            break;
	
			        for(int c=0;c<4;c++) {
			            if(found)
			                break;
			            if(c==a || c==b) {
			                continue;
			            }
			            for(int d=0;d<4;d++) {
			                if(found)
			                    break;
			                if(d==a || d==b || d==c){
			                    continue;
			                }
			                if(arr[c]<arr[d]) {
			                    int temp = arr[c];
			                    arr[c] = arr[d];
			                    arr[d] = temp;
			                }
			                if(arr[c] == 0 || arr[d] < 0) {
			             
			                    break;
			                }
			             
			                if((((long)arr[a]+arr[b]) * (long)(arr[a]-arr[b]))/arr[c] == 4) {
			                
			                    int aa = (int)(((long)arr[a] + (long)arr[b])/2);
			                    int bb = arr[a] - aa;
			                 
			                    if(aa>=1 && bb>=1 && aa<=10000 && bb<=10000 && (aa/bb == arr[d])){
			                        found = true;
			                        System.out.println(aa + " " + bb);
			                    }
			                }
			            }
			        }
			    }
			}
			if(!found) {
			    System.out.println("-1 -1");
			}
		}
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
				    tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
				    throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Related:

Leave a Comment

19 − seven =