|
Given an array arr[] of length N. The task is to replace all elements such that (arr[i] = arr[i]-origin) for all i. The origin of a positive integer is determined by iteratively summing its digits until only a single digit remains. Value of N doesn’t exceed 1000.
Examples:
Input: arr[]={16,15,213}
Output: {9,9,207}
Explanation:
- The sum of digits of 16 is (1+6)=7 which is single digit so origin of 16 is 7.
- The sum of digits of 15 is (1+5)=6 which is single digit so origin of 15 is 6.
- The sum of digits of 16 is (2+1+3)=6 which is single digit so origin of 213 is 6.
Input: arr[]={99,100,101}
Output: {90,99,99}
Explanation:
- The sum of digits of 16 is (9+9)=18. Again, (1+8)=9 which is single digit so origin of 99 is 9.
- The sum of digits of 16 is (1+0+0)=1 which is single digit so origin of 100 is 1.
- The sum of digits of 16 is (1+0+1)=2 which is single digit so origin of 101 is 2.
Approach:
Iterate the array with help of loop and find origin of each element with origin function. And update the array as (arr[i] = arr[i]-origin). The origin function takes a positive integer and iteratively sum its digits until only a single digit remains.
Below is the implementation of the above approach:
C++
#include <iostream>
#include <vector>
using namespace std;
// Function to find origin of a positive integer.
// This function takes a positive value as parameter.
int origin(int n)
{
// This ans will always keep value in single digit if it
// is greater it will make it single digit.
int ans = 0;
while (n > 0) {
// rem will keep last digit of number.
int rem = n % 10;
// we eliminate last digit of n.
n /= 10;
// ans is updated with adding last digit of n.
ans += rem;
// This will always make ans of one digit.
while (ans > 9) {
int rem = ans % 10;
ans /= 10;
ans += rem;
}
}
return ans;
}
int main()
{
int N = 3;
vector<int> A = { 99, 100, 101 };
// We iterate the loop and update also.
for (int i = 0; i < N; i++) {
// Here origin function gives a single digit origin
// value.
A[i] = A[i] - origin(A[i]);
}
for (int i = 0; i < N; i++) {
cout << A[i] << " " << endl;
}
return 0;
}
import java.util.ArrayList;
public class Main {
// Function to find origin of a positive integer.
// This function takes a positive value as parameter.
public static int origin(int n)
{
// This ans will always keep value in single digit
// if it is greater it will make it single digit.
int ans = 0;
while (n > 0) {
// rem will keep last digit of number.
int rem = n % 10;
// we eliminate last digit of n.
n /= 10;
// ans is updated with adding last digit of n.
ans += rem;
// This will always make ans of one digit.
while (ans > 9) {
rem = ans % 10;
ans /= 10;
ans += rem;
}
}
return ans;
}
public static void main(String[] args)
{
int N = 3;
ArrayList<Integer> A = new ArrayList<>();
A.add(99);
A.add(100);
A.add(101);
// We iterate the loop and update also.
for (int i = 0; i < N; i++) {
// Here origin function gives a single digit
// origin value.
A.set(i, A.get(i) - origin(A.get(i)));
}
for (int i = 0; i < N; i++) {
System.out.println(A.get(i) + " ");
}
}
}
def origin(n):
ans = 0
while n > 0:
rem = n % 10
n //= 10
ans += rem
while ans > 9:
rem = ans % 10
ans //= 10
ans += rem
return ans
if __name__ == "__main__":
N = 3
A = [99, 100, 101]
# We iterate the loop and update also.
for i in range(N):
# Here origin function gives a single digit origin value.
A[i] -= origin(A[i])
for i in range(N):
print(A[i])
// Function to find origin of a positive integer.
// This function takes a positive value as parameter.
function origin(n) {
// This ans will always keep value in single digit if it is greater it will make it single digit.
let ans = 0;
while (n > 0) {
// rem will keep last digit of number.
let rem = n % 10;
// we eliminate last digit of n.
n = Math.floor(n / 10);
// ans is updated with adding last digit of n.
ans += rem;
// This will always make ans of one digit.
while (ans > 9) {
rem = ans % 10;
ans = Math.floor(ans / 10);
ans += rem;
}
}
return ans;
}
function main() {
const N = 3;
const A = [99, 100, 101];
// We iterate the loop and update also.
for (let i = 0; i < N; i++) {
// Here origin function gives a single digit origin value.
A[i] = A[i] - origin(A[i]);
}
for (let i = 0; i < N; i++) {
console.log(A[i] + " ");
}
}
main();
// This code is contributed by Ayush Mishra
Time Complexity: O(n)*O(log(n)), where n is length of the each element of array.
Auxiliary Space: O(1)
|
Array Data Structure Guide