Skip to main content

Google kickstart 2022 round A | Challenge Nine (8pts, 12pts) solution

 

Problem: 

  
 

Ada gives John a positive integer N. She challenges him to construct a new number (without leading zeros), that is a multiple of 9, by inserting exactly one digit (0  9) anywhere in the given number N. It is guaranteed that N does not have any leading zeros.

As John prefers smaller numbers, he wants to construct the smallest such number possible. Can you help John?

Input

The first line of the input gives the number of test cases, TT test cases follow.

Each test case has a single line containing a positive integer N: the number Ada gives John.

Output

For each test case, output one line containing Case #xy, where x is the test case number (starting from 1) and y is the new number constructed by John. As mentioned earlier, y cannot have leading zeros.

Limits

Memory limit: 1 GB.
1T100.

Test Set 1

Time limit: 20 seconds.
1N105.

Test Set 2

Time limit: 40 seconds.
For at most 10 cases:
1N10123456.
For the remaining cases:
1N105.

Sample

Sample Input

3
5
33
12121
Sample Output

Case #1: 45
Case #2: 333
Case #3: 121212

In Sample Case #1, there are only two numbers that can be constructed satisfying the divisibility constraint: 45 and 54. John chooses the smaller number.

In Sample Case #2, 333 is the only number possible.

In Sample Case #3, there are four possible options - 212121122121121221 and 121212 - out of which the smallest number is 121212.

solution :

#include<bits/stdc++.h>

using namespace std ;

int sum_digits(string &n)

{

    int len = n.length();

    int sum = 0;

    for(int i = 0 ; i < len ; i++)

    {

        sum = sum + (n[i]-48) ;

        

    }

    return sum ;

}

string convert(string &n)

{  

    string new_str;

    int len = n.length();

    int req_digit = 9 - sum_digits(n)%9;

    if(req_digit == 9)

    {     

        

        n.insert(1 , "0");

    }

    else

    {

         int flag = 0 ; 

         char s = req_digit+48;

         for(int i =0 ; i < len ; i++)

        {

            if(s < n[i] && flag ==0 )

            { 

                

               flag = 1;

               n.insert(i,string(1,s));

                break;

            }

             

        }

          if(flag ==0  )

          n.insert(len,string(1,s));

        

         

        

    }

        

    return n;    

    

}

int main()

{

    int t ;

    cin >> t;

    for(int i =1 ; i <= t ; i++)

    {

        string  n ;

        cin >> n ;

        n = convert(n);

        cout <<"Case #"<<i <<": " << n << "\n";

    }

}


refrences : 

how-to-insert-single-character-using insert() and string() in c++





Comments

Popular posts from this blog

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...

Regular Expression Matching Leetcode Solution

Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a"  Output: false  Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*"  Output: true  Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*"  Output: true  Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase Englis...