Home » Interview coding problems/challenges

Google CodeJam 2019 | Foregone Solution

Here, we are implementing the solution of Google CodeJam 2019 (Foregone solution), which was asked in online qualifier round.
Submitted by Debasis Jana, on April 19, 2019

This problem was asked in Google CodeJam 2019 online qualifier round.

Problem Statement:

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an oversized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a 4... and the 4 key on the keyboard of our oversized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with an integer N.

Output

For each test case, output one line containing Case #x: A B, where x is the test case number (starting from 1), and A and B are positive integers as described above.

It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them.

Sample

Input	Output
3 4940 4444	Case #1: 2 2 Case #2: 852 88 Case #3: 667 3777

Reference: Foregone Solution

Explanation:

In Sample Case #1, notice that A and B can be the same. The only other possible answers are 1 3 and 3 1.

Note: Before going to solution, please try it by yourself.

Short description of solution approach

For any number N, let say, 45234, we can write it as 45234 + 00000 that is N = A+B, where A = 45234 and B = 00000. But, according to given condition there should not be any '4' in A or B. So, whenever we encounter '4' in A we can write it as 2 and at the same position at B we can put 2.

Example:

    Input: 45234
        Step 1: 
        45234	← A
        +00000  ← B
        --------------------------------
        45234   ← N
        ---------------------------------
        Step 2:
        25232   ← A
        +20002  ← B
        --------------------------
        45234	← N
        ---------------------------

So, after step 2, we can see that there is no 4 in A or B.

Note: You can replace it as 3 and 1 also. There may be multiple solutions but you must have to fulfill the condition.

Algorithm

    Step1: Take input N (as a string)
    Step2: Take an array B of size N and initialize all values to 0
    Step3: for(i=0;i<N.length();i++)
	    Step3.1: if(N[i]=='4')
		         B[i]='2';
		         N[i]=2;
    Step4: print N (that is A) and B

Explanation

Please read "Short description of sloution approach" section given above.

C++ implementation:

#include <bits/stdc++.h>
#define ll long long int;

using namespace std;
int main()
{
	int T,k=1;
	
	cin>>T;
	
	while(T--)
	{
		string N;
		cin>>N;
		int i,len=0;
		len=N.length();         //Length of N
		//Taking vector B of size len (Size of N) 
		//and initialize all values to 0
		vector<int>B(len,0);
		for(i=0;i<len;i++)
		{
			//Checking if N[i] is 4 or not
			if(N[i]=='4')
			{
				N[i]='2';       //If 4 replace it by 2
				B[i]=2;         //Also replace B[i] by 2
			}
		}

		int ind=-1;
		/*If there is any leading 0 in B then we should not print that. 
		So, moving the index to very first non zero value of B*/
		for(i=0;i<len;i++)
		{
			//checking if there is any more leading 0 or not
			if(B[i]!=0)     
			{
				ind=i;
				break;
			}
		}
		
		//printing the value of A
		cout<<"Case #"<<k<<": "<<N<<" ";        
		//printing the value of B without leading 0
		for(i=ind;i<len;i++)
			cout<<B[i];
		cout<<"\n";
		//k is for printing the Case Number
		k++;
	}
	
	return 0;
}

Output