Find the Mobile Number formed using first digits of arrays of absolute differences of consecutive numbers
Given a String ph[], the task is to find a new number for the user, based on following conditions:
- The new number will also start from the same digit as of original number.
- The digits of the new number will be the first digits of a series of arrays of absolute differences of the consecutive elements.
Examples:
Input: ph = “9827218706”
Output: 9154301011
Explanation:Input: ph =”9647253846″
Output: 9310100011
Approach: Consider the following steps to solve this problem:
- Convert every character from the string into integer and store it into the array ph1[] using list comprehension.
- Declare an empty string ph2.
- Convert first element of array ph1[ ] into a string and add it to ph2.
- Using List comprehension create an array by storing the absolute difference of consecutive elements.
- Assign this array to ph1.
- Repeat step 3-5, ten times as the phone number have ten digits.
Below is the implementation of the above approach.
Java
// Java program for above approach public class Mobile { // Function to find lucky phone number static String phone(String ph, int n) { // Converting char to int and storing into array. int [] ph1 = new int [n]; for ( int i = 0 ; i < n; i++) ph1[i] = ph.charAt(i) - '0' ; // Empty string to store lucky number. String ph2 = "" ; // Loop for performing action // and adding digit to ph2. for ( int i = 0 ; i < n; i++) { // Convert first element into // string and adding to ph2. ph2 += ph1[ 0 ]; // Creating new ph1 by subtracting // consecutive element. int ph3[] = new int [ph1.length - 1 ]; for ( int j = 0 ; j < ph1.length - 1 ; j++) ph3[j] = Math.abs(ph1[j] - ph1[j + 1 ]); ph1 = ph3; } // Return lucky number ph2 return ph2; } // Driver code public static void main(String[] args) { // Original number String ph = "9827218706" ; // Calling phone function. String num = phone(ph, ph.length()); // Print the lucky number System.out.println(num); } } // This code is contributed by Lovely Jain |
Python3
# Function to find lucky phone number def phone(ph, n): # Converting char to int and storing into array. ph1 = [ int (i) for i in ph] # Empty string to store lucky number. ph2 = "" # Loop for performing action # and adding digit to ph2. for _ in range (n): # Convert first element into # string and adding to ph2. ph2 + = str (ph1[ 0 ]) # Creating new ph1 by subtracting # consecutive element. ph1 = [ abs (ph1[j] - ph1[j + 1 ]) \ for j in range ( len (ph1) - 1 )] # Return lucky number ph2 return ph2 # Original number ph = "9827218706" # Calling phone function. num = phone(ph, len (ph)) # Print the lucky number print (num) |
C#
// C# program for above approach using System; public class Mobile { // Function to find lucky phone number static String phone(String ph, int n) { // Converting char to int and storing into array. int [] ph1 = new int [n]; for ( int i = 0; i < n; i++) ph1[i] = ph[i] - '0' ; // Empty string to store lucky number. String ph2 = "" ; // Loop for performing action // and adding digit to ph2. for ( int i = 0; i < n; i++) { // Convert first element into // string and adding to ph2. ph2 += ph1[0]; // Creating new ph1 by subtracting // consecutive element. int [] ph3 = new int [ph1.Length - 1]; for ( int j = 0; j < ph1.Length - 1; j++) ph3[j] = Math.Abs(ph1[j] - ph1[j + 1]); ph1 = ph3; } // Return lucky number ph2 return ph2; } // Driver code public static void Main() { // Original number String ph = "9827218706" ; // Calling phone function. String num = phone(ph, ph.Length); // Print the lucky number Console.Write(num); } } // This code is contributed by Saurabh Jaiswal |
Javascript
<script> // Function to find lucky phone number function phone(ph, n) { // Converting char to int and storing into array. let ph1 = []; for (i of ph) ph1.push(i) // Empty string to store lucky number. let ph2 = "" // Loop for performing action // and adding digit to ph2. for (let _ = 0; _ < n; _++) { // Convert first element into // string and adding to ph2. ph2 += new String(ph1[0]) // Creating new ph1 by subtracting // consecutive element. let temp = [] for (let j = 0; j < ph1.length - 1; j++) { temp.push(Math.abs(ph1[j] - ph1[j + 1])) } ph1 = temp } // Return lucky number ph2 return ph2 } // Original number let ph = "9827218706" // Calling phone function. let num = phone(ph, ph.length) // Print the lucky number document.write(num) // This code is contributed by gfgking. </script> |
C++
#include <iostream> #include <cmath> #include <string> #include <vector> using namespace std; // Function to find lucky phone number string phone(string ph, int n) { // Vector to store the digits of the phone number vector< int > ph1; for ( int i = 0; i < n; i++) { // Convert each character to its numerical value ph1.push_back(ph[i] - '0' ); } // Empty string to store the lucky phone number string ph2 = "" ; // Loop to perform the operations and add the digits to ph2 for ( int i = 0; i < n; i++) { // Convert the first element to a string and add it to ph2 ph2 += to_string(ph1[0]); // Create a new vector ph3 by subtracting consecutive elements vector< int > ph3; for ( int j = 0; j < ph1.size() - 1; j++) { ph3.push_back( abs (ph1[j] - ph1[j + 1])); } ph1 = ph3; } // Return the lucky phone number return ph2; } int main() { // Original phone number string ph = "9827218706" ; // Call the phone function string num = phone(ph, ph.length()); // Print the lucky phone number cout << num << endl; return 0; } #This code is contributed by Edula Vinay Kumar Reddy |
9154301011
Time Complexity: O(N*N), The time complexity is O(N*N) because there are two nested loops in the “phone()” function. The first loop iterates over each digit of the input phone number, which takes O(N) time. The second loop also iterates over each digit of the phone number, but it creates a new vector “ph3” by subtracting consecutive elements. This operation takes O(N) time because it performs N-1 subtractions. Therefore, the overall time complexity of the algorithm is O(N*N).
Auxiliary Space: O(N), The space complexity is O(N) because the algorithm uses two vectors to store the digits of the input phone number and the difference between consecutive digits. Both vectors have a maximum length of N, which is the length of the input phone number. Therefore, the space complexity is O(N).
Efficient Approach: In this approach, no extra space is required for storing elements in the array. First, declare an empty string ph2 in which lucky number will be stored, now create a for loop in which the first character of the string will be added to ph2 and again another for loop to find the absolute difference of consecutive element. Now the string of absolute difference will be assigned to ph1 which is the original number and the same steps will be followed. Follow the steps below to solve the problem:
- Initialize a string variable ph2[] as an empty string.
- Iterate over the range [0, N) using the variable i and perform the following tasks:
- Add ph[0] to the variable ph2[].
- Initialize a string variable S[] as an empty string.
- Iterate over the range [0, N-1) using the variable j and perform the following tasks:
- Add the value of str(abs(int(ph[j])-int(ph[j+1]))) to the variable S[].
- Set the value of ph as S[].
- After performing the above steps, print the value of ph2[] as the answer.
Below is the implementation of the above approach.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find lucky number. string phone(string ph, int n) { // ph2 is empty string to store lucky number. string ph2 = "" ; // For loop for finding lucky number for ( int i = 0; i < ph.length(); i++) { // Add first element of ph to ph2 ph2 += ph[0]; // S for storing the difference string S = "" ; // Loop to calculate the absolute difference for ( int j = 0; j < ph.length(); j++) { int x = abs ( int (ph[j]) - int (ph[j + 1])); S += x + '0' ; } // Assigning S to ph. ph = S; } // Return the lucky number return ph2; } // Driver Code int main() { // Original number string ph = "9827218706" ; // Call phone function string num = phone(ph, ph.length()); // Printing lucky number cout << (num); } // This code is contributed by Potta Lokesh |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find lucky number. static String phone(String ph, int n) { // ph2 is empty string to store lucky number. String ph2 = "" ; // For loop for finding lucky number for ( int i = 0 ; i < ph.length(); i++) { // Add first element of ph to ph2 ph2 += ph.charAt( 0 ); // S for storing the difference String S = "" ; // Loop to calculate the absolute difference for ( int j = 0 ; j < ph.length()- 1 ; j++) { int x = Math.abs(ph.charAt(j) - ph.charAt(j+ 1 )); S += ( char )(x + '0' ); } // Assigning S to ph. ph = S; } // Return the lucky number return ph2; } // Driver Code public static void main(String args[]) { // Original number String ph = "9827218706" ; // Call phone function String num = phone(ph, ph.length()); // Printing lucky number System.out.println(num); } } // This code is contributed by avijitmondal1998 |
Python3
# Function to find lucky number. def phone(ph, n): # ph2 is empty string to store lucky number. ph2 = "" # For loop for finding lucky number for i in range ( len (ph)): # Add first element of ph to ph2 ph2 + = ph[ 0 ] # S for storing the difference S = "" # Loop to calculate the absolute difference for j in range ( len (ph) - 1 ): x = abs ( int (ph[j]) - int (ph[j + 1 ])) S + = str (x) # Assigning S to ph. ph = S # Return the lucky number return ph2 # Original number ph = "9827218706" # Call phone function num = phone(ph, len (ph)) # Printing lucky number print (num) |
C#
// C# code for the above approach using System; class GFG { // Function to find lucky number. static string phone( string ph, int n) { // ph2 is empty string to store lucky number. string ph2 = "" ; // For loop for finding lucky number for ( int i = 0; i < ph.Length; i++) { // Add first element of ph to ph2 ph2 += ph[0]; // S for storing the difference string S = "" ; // Loop to calculate the absolute difference for ( int j = 0; j < ph.Length; j++) { int x = Math.Abs(ph[j] - ph[j + 1]); S += x + '0' ; } // Assigning S to ph. ph = S; } // Return the lucky number return ph2; } // Driver Code public static void Main() { // Original number string ph = "9827218706" ; // Call phone function string num = phone(ph, ph.Length); // Printing lucky number Console.WriteLine (num); } } // This code is contributed by ukasp. |
Javascript
<script> // javascript program for the above approach // Function to find lucky number. function phone( ph , n) { // ph2 is empty string to store lucky number. // Converting char to int and storing into array. let ph1 = []; for (i of ph) ph1.push(i) // Empty string to store lucky number. let ph2 = "" // Loop for performing action // and adding digit to ph2. for (let _ = 0; _ < n; _++) { // Convert first element into // string and adding to ph2. ph2 += new String(ph1[0]) // Creating new ph1 by subtracting // consecutive element. let S = [] for (let j = 0; j < ph1.length - 1; j++) { S.push(Math.abs(ph1[j] - ph1[j + 1])) } ph1 = S } // Return the lucky number return ph2; } // Driver Code // Original number var ph = "9827218706" ; // Call phone function var num = phone(ph, ph.length); // Printing lucky number document.write(num); // This code is contributed by umadevi9616 </script> |
9154301011
Time Complexity: O(N*N), The code has a nested for loop. The outer loop runs N times, where N is the length of the input string. The inner loop also runs N times, where for each iteration, the difference between two adjacent characters of the input string is calculated. Therefore, the total time complexity of the code is O(N*N).
Auxiliary Space: O(N),The code uses a few variables to store the input and output strings. The input string and the lucky number string are stored as strings, and therefore, they use O(N) space, where N is the length of the input string. The difference string S also uses O(N) space. Therefore, the total space complexity of the code is O(N).